4

我必须计算 N 维空间中两点之间的欧几里得距离，速度至关重要。我有两个 C 风格的浮点数组，代表 N 维空间中的两个点。

它们之间距离的公式是（^ 只是表示的幂，而不是 XOR）： 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。

4

2 回答 2

2

绝对摆脱pow()。对此的大部分优化取决于您如何使用它。您是否对非常大的 N 执行一次此操作并且花费的时间太长？或者，更有可能的是，您是否在一个紧密的循环中多次执行此操作？

如果您使用非常大的 N（>1000 左右），则有高度优化的数值库可以做到这一点。例如，BLAS 有一个*nrm2函数可以计算欧几里得范数（dnrm2, snrm2, cnrm2, znrm2, 取决于数据类型 [single, double, complex single, complex double]）。 对于某些处理器架构， GotoBLAS可能是最快的。 MKL具有英特尔手动调整的 BLAS 实施，但它不是免费的。最后，ATLAS是一个实现 BLAS 的自调整库。

如果你有一个 N 很小或不太大的紧密循环，那么你可能需要进行一些手动调整以使其更快。-O3您可以使用或-ftree-vectorize编译器标志打开自动矢量化。您也可以手动进行矢量化，但学习如何执行此操作可能会很痛苦。

您可以进行循环展开（即，将 N 分成例如 4 的块，并在 for 循环体内显式写出 4 个连续值的计算。这具有欺骗编译器使用更多寄存器进行即时计算的效果---并且寄存器是您必须使用的最快的内存形式。此外，您可以利用预取（通过一次内存访问调用读取一段数据）。

Another thing to do in this situation is to try overwriting one of your inputs. That is, maybe you could get away with writing the output into p or q. This helps because the positions of p that you compute will still be in the cache when you are ready to write. Caches often won't write the data to memory unless they absolutely have to---one reason is that the cache line is needed and we need to kick the last one out. You use fewer cache lines by writing to one of your inputs.

There are a half million other things to try, but I think I'll stop here. Good luck!

于 2012-08-24T04:21:09.360 回答
0

我永远不会使用 pow() - 如果没有分析，我的猜测是这会减慢你的速度。

你需要做一个温度，然后把它平方。

double diff = p[i] - q[i];
sum += diff*diff;

sqrt 有点慢，但这里唯一的选择是一些近似值。如果您的 N > 大约 10，则 sqrt 可能不会成为瓶颈。

还有像 boost 等库可能会加快速度，但首先尝试摆脱 pow()。请记住 diff*diff 是一个浮点指令，其中 pow() 是为非整数幂等设计的整个程序。

于 2012-08-24T03:58:36.867 回答