c - 用c计算欧氏距离的最快方法

Question

我需要以最快的方式计算两点之间的欧氏距离。 在 C 中。

我的代码是这样的，看起来有点慢:

float distance(int py, int px, int jy, int jx){
     return sqrtf((float)((px)*(px)+(py)*(py)));
}

提前致谢。

编辑:

对不起，我没说清楚。 我最好指定上下文: 我正在处理图像，我需要从每个像素到所有其他像素的欧氏距离。 所以我必须计算很多次。我不能使用距离的平方。 为了更清楚，我将添加更多代码:

for (jy=0; jy<sizeY; jy++) {
        for (jx=0; jx<sizeX; jx++) {
            if (jx==px && jy==py) {
                ;
            }
            else{
                num+=rfun(imgI[py][px].red-imgI[jy][jx].red)/distance(py, px, jy, jx);
                den+=RMAX/distance(py, px, jy, jx);
            }
        }
    }


 float distance(int py, int px, int jy, int jx){
     return sqrtf((float)((px-jx)*(px-jx)+(py-jy)*(py-jy)));
}

那是我没有做的。我必须用所有像素(px，py)来做

编辑2: 对不起，我不清楚，但我尽量让这个问题尽可能笼统。 我正在编写一个程序来使用算法处理图像。最大的问题是时间，因为我必须非常非常快地完成它。现在我需要优化的是这个功能: `float normC(int py, int px, int color, pixel** imgI, int sizeY, int sizeX){

int jx, jy;
float num=0, den=0;
if (color==R) {
    for (jy=0; jy<sizeY; jy++) {
        for (jx=0; jx<sizeX; jx++) {
            if (jx==px && jy==py) {
                ;
            }
            else{
                num+=rfun(imgI[py][px].red-imgI[jy][jx].red)/distance(py, px, jy, jx);
                den+=RMAX/distance(py, px, jy, jx);
            }
        }
    }
}
else if (color==B){
    for (jy=0; jy<sizeY; jy++) {
        for (jx=0; jx<sizeX; jx++) {
            if (jx==px && jy==py) {
                ;
            }
            else{
                num+=rfun(imgI[py][px].blue-imgI[jy][jx].blue)/distance(py, px, jy, jx);
                den+=RMAX/distance(py, px, jy, jx);
            }
        }
    }
}
else if (color==G){
    for (jy=0; jy<sizeY; jy++) {
        for (jx=0; jx<sizeX; jx++) {
            if (jx==px && jy==py) {
                ;
            }
            else{
                num+=rfun(imgI[py][px].green-imgI[jy][jx].green)/distance(py, px, jy, jx);
                den+=RMAX/distance(py, px, jy, jx);
            }
        }
    }
}

return num/den;

} `

此函数在每个像素 (px; py) 的循环中被调用，因此它被调用了很多次并且需要很多时间来计算它。 rfun 函数不可优化，因为它已经非常简单和快速。 我需要做的是使距离函数更快。

1)我试过 hypotf 但它比 distance 函数慢

2)我增加了编译器的优化设置，使过程快了 2 倍!

3) 我尝试使用宏 #define DIST(x, y) sqrtf((float)((x)*(x)+(y)*(y))) 但没有改变了(如我所料)

编辑3:

最后我发现最快的方法是计算所有可能的距离并将它们存储在一个数组中，然后再开始循环计算 normC 函数。 为了让它更快，我计算了距离的倒数，这样我就可以使用乘积而不是商:

float** DIST    
DIST=malloc(500*sizeof(float*)); //allocating memory for the 2d array
for (i=0; i<500; i++) {
    DIST[i]=malloc(500*sizeof(float));
}

for(i=0; i<500; i++){      //storing the inverses of the distances
    for (p=0; p<500; p++) {
        DIST[i][p]= 1.0/sqrtf((float)((i)*(i)+(p)*(p)));
    }
}
float normC(int py, int px, int color, pixel** imgI, int sizeY, int sizeX){

int jx=0, jy=0;
float num=0, den=0;
if (color==R) {
    for (jy=0; jy<sizeY; jy++) {
        for (jx=0; jx<sizeX; jx++) {
            if (jx==px && jy==py) {
                ;
            }
            else if (py>=jy && px>=jx){
                num+=rfun(imgI[py][px].red-imgI[jy][jx].red)*DIST[py-jy][px-jx];
                den+=DIST[py-jy][px-jx];
            }
            else if (jy>py && px>=jx){
                num+=rfun(imgI[py][px].red-imgI[jy][jx].red)*DIST[jy-py][px-jx];
                den+=DIST[jy-py][px-jx];
            }
            else if (jy>py && jx>px){
                num+=rfun(imgI[py][px].red-imgI[jy][jx].red)*DIST[jy-py][jx-px];
                den+=DIST[jy-py][jx-px];
            }
        }
    }
}
else if (color==B){
    for (jy=0; jy<sizeY; jy++) {
        for (jx=0; jx<sizeX; jx++) {
            if (jx==px && jy==py) {
                ;
            }
            else if (py>=jy && px>=jx){
                num+=rfun(imgI[py][px].blue-imgI[jy][jx].blue)*DIST[py-jy][px-jx];
                den+=DIST[py-jy][px-jx];
            }
            else if (jy>py && px>=jx){
                num+=rfun(imgI[py][px].blue-imgI[jy][jx].blue)*DIST[jy-py][px-jx];
                den+=DIST[jy-py][px-jx];
            }
            else if (jy>py && jx>px){
                num+=rfun(imgI[py][px].blue-imgI[jy][jx].blue)*DIST[jy-py][jx-px];
                den+=DIST[jy-py][jx-px];
            }
        }
    }
}
else if (color==G){
    for (jy=0; jy<sizeY; jy++) {
        for (jx=0; jx<sizeX; jx++) {
            if (jx==px && jy==py) {
                ;
            }
            else if (py>=jy && px>=jx){
                num+=rfun(imgI[py][px].green-imgI[jy][jx].green)*DIST[py-jy][px-jx];
                den+=DIST[py-jy][px-jx];
            }
            else if (jy>py && px>=jx){
                num+=rfun(imgI[py][px].green-imgI[jy][jx].green)*DIST[jy-py][px-jx];
                den+=DIST[jy-py][px-jx];
            }
            else if (jy>py && jx>px){
                num+=rfun(imgI[py][px].green-imgI[jy][jx].green)*DIST[jy-py][jx-px];
                den+=DIST[jy-py][jx-px];
            }
        }
    }
}

return num/(den*RMAX);
}

Answer 1

平方根是一个昂贵的函数。如果你只关心距离如何比较(这个距离小于这个距离，相等等等)， 你不需要平方根。

这与许多数字信号处理框架的原因基本相同 (X-Midas、Midas 2k、PicklingTools)有 magnitude(这基本上是复数的相同距离计算)和 magnitude2(省略平方根)。有时您只关心事物的比较方式，不一定是实际值。