N维空间中两点间欧氏距离的最快速算法
我必须计算N维空间中两点之间的欧几里得距离，而速度是至关重要的。我有两个C风格的浮点数组，表示N维空间中的两个点。
它们之间的距离公式是(^只是表示幂的幂，而不是异或)：sqrt(sum((p1-q1)^2 + (p2-q1)^2 + ....(pn-qn)^2)
我当前的代码如下所示：
sum = 0;
for(int i=0;i<N;++i){
sum += pow(p[i]-q[i],2);
sqrt(sum)这段代码相当慢，我想知道是否有库可以加快速度？我想有人已经用c编写了一个关于在数组上执行数学运算的快速库，它可以让我快速地对数组进行元素级的运算。
编辑:作为对nevsan的回答，我正在用一个小N做很多计算，大约是10或20。
回答 2
Stack Overflow用户
发布于 2012-08-24 12:21:09
一定要摆脱pow()。这方面的优化很大程度上取决于您如何使用它。你是不是对非常大的N做了一次，而且时间太长了？或者，更有可能的是，您是否在一个紧凑的循环中多次执行此操作？
如果您使用的是非常大的N (>1000左右)，那么有一些高度优化的数值库可以做到这一点。例如，BLAS具有计算欧几里得范数(dnrm2、snrm2、cnrm2、znrm2，取决于数据类型single、double、complex single、complex double)的*nrm2函数。对于某些处理器架构，GotoBLAS可能是最快的。MKL采用了英特尔手动调整的BLAS实现，但它不是免费的。最后，ATLAS是一个实现BLAS的自调优库。
如果你有一个小的或者不是很大的N的紧密循环，那么你可能需要做一些手动调整来获得更快的速度。您可以使用-O3或-ftree-vectorize编译器标志打开自动矢量化。您也可以手动进行矢量化，但学习如何做到这一点可能会很痛苦。
您可以执行循环展开(也就是，将N分成例如4的块，并显式地写出for循环体中4个连续值的计算结果。这会诱使编译器使用更多的寄存器进行即时计算-寄存器是您必须使用的最快的内存形式。此外，您还可以利用预取(通过一次内存访问调用读取一段数据)。
在这种情况下要做的另一件事是尝试覆盖您的输入之一。也就是说，也许您可以将输出写入p或q。这很有帮助，因为当您准备好写入时，您计算的p的位置仍将在缓存中。缓存通常不会将数据写入内存，除非它们是绝对必要的-原因之一是需要缓存线，而我们需要踢出最后一个缓存线。通过写入您的输入之一，可以使用更少的缓存线。
还有50万种其他东西可以尝试，但我想我就到此为止了。祝好运!
Stack Overflow用户
发布于 2012-08-24 11:58:37
我永远不会使用pow() --我的猜测是，没有分析的情况下，这会大大降低你的速度。
你需要做一个临时工，然后把它平方。
double diff = p[i] - q[i];
sum += diff*diff;sqrt有点慢，但这里唯一的选项是一些近似值。如果N>大于10，那么sqrt将不会成为瓶颈。
还有一些库，如boost等，可能会加快速度，但首先试着去掉pow()。记住，diff*diff是一个浮点指令，其中的power()是为非整数幂等设计的整个程序。
https://stackoverflow.com/questions/12102899
复制相似问题
腾讯云开发者
