c - 在 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 之外不能有更近的邻居。

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