有序数的有效稳定和

Question

我有一个很长的浮点正数列表（std::vector<float>，大小约为 1000）。这些数字按降序排列。如果我按照顺序对它们求和：

for (auto v : vec) { sum += v; }

我想我可能会遇到一些数值稳定性问题，因为接近向量末尾的 sum 会比 v 大得多。最简单的解决方案是以相反的顺序遍历向量。我的问题是：这和前向案例一样有效吗？我会丢失更多缓存吗？

还有其他智能解决方案吗？

Answer 1

为此，您可以在 std::vector<float> vec:

中使用不带任何换位的反向迭代器

float sum{0.f};
for (auto rIt = vec.rbegin(); rIt!= vec.rend(); ++rIt)
{
    sum += *rit;
}

或者使用标准算法做同样的工作：

float sum = std::accumulate(vec.crbegin(), vec.crend(), 0.f);

性能必须相同，仅更改了向量的旁路方向

Answer 2

The easiest solution would be to traverse the vector in reverse order. My question is: is that efficient as well as the forward case? I will have more cache missing?

是的，它很有效。硬件的分支预测和智能缓存策略针对顺序访问进行了调整。您可以安全地累积您的向量：

#include <numeric>

auto const sum = std::accumulate(crbegin(v), crend(v), 0.f);

Answer 3

I guess I can have some numerical stability problem

所以测试一下。目前你有一个假设性的问题，也就是说，完全没有问题。

如果您进行测试，并且假设变成了实际问题，那么您应该担心实际修复它。

即 - 浮点精度可能会导致问题，但您可以先确认它是否真的适用于您的数据，然后再将其优先于其他所有内容。

... I will have more cache missing?

1000 个浮点数是 4Kb - 它适合现代大众市场系统的缓存（如果您有其他平台，请告诉我们它是什么）。

唯一的风险是预取器在向后迭代时不会帮助您，但是您的矢量当然可能已经在缓存中。除非您在完整程序的上下文中进行概要分析，否则您无法真正确定这一点，因此在您拥有完整程序之前不必担心它。

Is there any other smart solution?

不要担心可能会成为问题的事情，直到它们真正成为问题为止。最多值得注意可能的问题，并构建您的代码，以便您可以在以后用仔细优化的解决方案替换最简单的解决方案，而无需重写其他所有内容。

Answer 4

我bench-marked您的用例和结果（见附图）指向向前或向后循环不会产生任何性能差异的方向。

您可能还想在硬件和编译器上进行测量。

使用 STL 执行求和，它与手动循环数据一样快，但表现力更强。

使用以下进行反向累加：

std::accumulate(rbegin(data), rend(data), 0.0f);

while forward accumulation:

std::accumulate(begin(data), end(data), 0.0f);

Answer 5

如果您所说的数值稳定性是指准确性，那么是的，您最终可能会遇到准确性问题。根据最大值与最小值的比率，以及您对结果准确性的要求，这可能是问题，也可能不是问题。

如果你确实想要高精度，那么可以考虑Kahan summation - this uses an extra float for error compensation. There is also pairwise summation。

精度与时间权衡的详细分析见this article。

C++17 更新：

其他一些答案提到了 std::accumulate。自 C++17 以来，有 execution policies 允许并行化算法。

例如

#include <vector>
#include <execution>
#include <iostream>
#include <numeric>

int main()
{  
   std::vector<double> input{0.1, 0.9, 0.2, 0.8, 0.3, 0.7, 0.4, 0.6, 0.5};

   double reduceResult = std::reduce(std::execution::par, std::begin(input), std::end(input));

   std:: cout << "reduceResult " << reduceResult << '\n';
}

这应该以非确定性舍入误差为代价更快地对大型数据集求和（我假设用户将无法确定线程分区）。

有序数的有效稳定和

Efficient stable sum of ordered numbers

c++

floating-point

precision