在3d空间中找到不足的最近邻居

Question

我的输入文件是一个csv文件，其数据结构如下;

5,3.5644,5.4556,3.5665
...
int_id,x_float,y_float,z_float

我有一个结构，它包含一个点的id和它的三个坐标。我需要根据欧几里德距离找到4个最接近的结构。我是通过天真的方法做到的，但有没有任何有效的方法来实现它？我读到了关于knn算法但它需要外部库。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>

//struct for input csv data
struct oxygen_coordinates
{
    unsigned int index; //index of an atom
    //x,y and z coordinates of atom 
    float x;
    float y;
    float z;
};

//Given the data in a line in a an inputfile, process it to put it in   oxygen_coordinates struct
struct oxygen_coordinates * line_splitter(struct oxygen_coordinates *data, const char *input)
{
    return (sscanf(input, "%u,%f,%f,%f", &data->index, &data->x, &data->y, &data->z) != 7)
            ? NULL : data;
}
//Distance function for two pints in a struct
float getDistance(struct oxygen_coordinates a, struct oxygen_coordinates b)
{
      float distance;
      distance = sqrt((a.x - b.x) * (a.x - b.x) + (a.y-b.y) *(a.y-b.y) + (a.z - b.z) * (a.z - b.z));
      return distance;
} 

//struct for neighbour distance and their indices
    struct nbrs_ind {
    float value;
    int index;
    };

// comparision function for sorting the neighbours -> qsort library
int cmp(const void *pa, const void *pb)
{
    struct nbrs_ind *pa1 = (struct nbrs_ind *)pa;
    struct nbrs_ind *pa2 = (struct nbrs_ind *)pb;
    if ((*pa1).value < (*pa2).value)
            return -1;
    else if ((*pa1).value > (*pa2).value)
            return 1;
    else
            return 0;
}
//main program
int  main(int argc, char *argv[])
{
    FILE *stream; // file pointer
    char *line = NULL; //line pointer
    size_t len = 0;
    ssize_t nread;
    struct oxygen_coordinates * atom_data = NULL; //pointer to oxygen_coordinate struct
    int numatoms = 0; // counter variable for number of atoms

    int i,j,k,p ; // loop initilizers
    //Check for correct number of arguments
    if (argc !=2 ) {
            fprintf(stderr, "Usage: %s <inputfile> <outputfile>\n", argv[0]);
            exit(EXIT_FAILURE);
    }
    //Open the input csv file given in the first argument
    stream = fopen(argv[1], "r");
    if (stream == NULL) {
            perror("fopen");
            exit(EXIT_FAILURE);
    }
    while ((nread = getline(&line, &len, stream)) != -1) {
            if ((atom_data = realloc(atom_data, (size_t) (numatoms + 1) * sizeof(struct oxygen_coordinates))) == NULL) {
                    fprintf(stderr, "error not enough memory");
                    exit(EXIT_FAILURE);
            }
            line_splitter(&atom_data[numatoms], line);
            numatoms = numatoms + 1;
    }
    free(line);
    fclose(stream);

    // All the data is read in memory in atom_data
    printf("-------------------------------------------\n");
    printf("There are %d atoms in the input file. \n", numatoms);
    printf("-------------------------------------------\n");


   // declare a global array that will hold the 4 nearest atom_data...
   float dist_mat[numatoms][numatoms] ;// create n by n matrix for  distances
    // Create a 2-D distnace matrix        
    for(j=0; j < numatoms; j++){
            for(k=0; k < numatoms; k++) {
                    dist_mat[j][k] = getDistance(atom_data[j], atom_data[k]);
                    printf("%f\t", dist_mat[j][k]);
            }
            printf("\n");
    }
    //now I sort every row from dist_mat and get the closest 4 
    // I need something like as follows
    ////knn(atom_data[query],atom_data,4);//this should return closest 4 points based on  Euclidean distances in atom_data
    free(atom_data);
    exit(EXIT_SUCCESS);
}

Answer 1

提高性能的一种方法是意识到您不需要实际距离。比较距离的平方就足够了，所以你可以跳过sqrt函数调用。

可能（但不一定）加快速度的另一件事是从计算x距离开始。使用距离总是正的事实，因此如果x距离比第四个最近的点总距离长，那么就不需要计算(a.y-b.y) *(a.y-b.y) + (a.z - b.z) * (a.z - b.z)。

如果您选择仅使用x值开始的方法，我还建议更改数据结构。不使用每个点的结构，而是使用四个数组：int *x, *y, *z, *indexes;这将使代码更加缓存友好。 （是的，指针和数组之间存在差异，但这里没有那么相关）

以上方法很容易调整。如果你想更高级，你可以使用这个想法。

1. 将空间划分为3D框的网格。
2. 计算哪些点属于哪个框并存储该信息。

看看这张图片：

例如，如果你在D4中有一个点，并且你想找到最接近的四个邻居，并且你在D4中找到一个邻居，那么你知道在方块C3：E5之外不能有更近的邻居。以相同的方式，在D4中具有D3中的邻居的点不能在区域B3：F6之外具有更近的邻居。

但优化的第一件事是始终确定瓶颈。你确定这是问题吗？你说你从文件中读取数据，从文件中读取一行应该比计算距离慢。

Answer 2

除了提到的平方根效率低，这些循环计算每对的距离两次。

for(j=0; j < numatoms; j++){
    for(k=0; k < numatoms; k++) {
        dist_mat[j][k] = getDistance(atom_data[j], atom_data[k]);
        printf("%f\t", dist_mat[j][k]);
    }
    printf("\n");
}

您可以通过仅计算每对的距离来将执行时间减半，如

for(j=0; j < numatoms-1; j++){
    for(k=j+1; k < numatoms; k++) {
        dist_mat[j][k] = dist_mat[k][j] = getDistance(atom_data[j], atom_data[k]);
        printf("%f\t", dist_mat[j][k]);
    }
    printf("\n");
}

当然，当j == k距离必须是0。