std::partial_sum和std::inclusive_scan有什么区别？

Question

在阅读关于std::inclusive_scan的内容时，似乎没有任何示例。
它给我留下了与std::partial_sum非常相似的印象。

partial_sum：

template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first,
                      InputIt last, OutputIt d_first );

inclusive_scan：

template< class InputIt, class OutputIt >
OutputIt inclusive_scan( InputIt first,
                         InputIt last, OutputIt d_first );

可以有人详细解释它们的差异吗？什么情况下我会选择其中之一？

- Trevor Hickey

Answer 1

std::inclusive_scan函数文档说明：

换句话说，求和操作可以以任意顺序执行。如果binary_op不是可结合的，则行为是不确定的。

std::partial_sum函数文档则明确表示：

*(d_first+k) = *first + *(first+1) + ... + *(first+k);

因此，std::inclusive_scan 仅在 binary_op 是可结合的情况下等价于 std::partial_sum，即当 (aopb)opc = aop(bopc) 时。

如果 binary_op 非可结合，则 std::partial_sum 会产生确定性结果，而您无法预测 std::inclusive_scan 的结果会是什么。

- Leon

Answer 2

std::inclusive_scan 是C++17标准库里并行编程的一部分，而std::partial_sum 则早在此之前就已存在。这两个函数都被重载了。如果您未指定运算符，则默认为 std::plus：

template< class InputIt, class OutputIt >
OutputIt partial_sum( InputIt first,
                      InputIt last, OutputIt d_first );

对于许多类型，如整数，其中std::plus是可结合的，partial_sum和inclusive_scan将是相同的。实际上，背后的算法相同，"inclusive scan"、"partial sum"等都是同一类型计算的同义词（维基百科称其为前缀和）。

不过，使用用户指定运算符的其他重载函数存在差异：

template< class InputIt, class OutputIt, class BinaryOperation >
OutputIt partial_sum( InputIt first, InputIt last, OutputIt d_first,
                      BinaryOperation op );

partial_sum的约束条件比inclusive_scan弱。它只要求op不能使任何迭代器失效或修改涉及范围内的任何元素。

并行化的问题在于它不需要op是可结合的。由于partial_sum按照其规定需要顺序执行，因此到目前为止还不需要这样做。缺点是它阻止了并行执行，因为你无法重新排序计算。

在inclusive_scan中，显式要求op是一个可结合的操作，否则会得到未定义的行为。然而，它的优点在于现在可以通过指定执行策略来更改代码以支持并行执行：

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryOperation >
ForwardIt2 inclusive_scan( ExecutionPolicy&& policy,
                           ForwardIt1 first, ForwardIt1 last,
                           ForwardIt2 d_first, BinaryOperation binary_op );

什么情况下我应该选择其中一个而不是另一个？

• 如果您的运算符是可结合的，我建议始终使用inclusive_scan。即使您总是使用顺序执行，它也可以作为某种形式的文档。

• 如果您知道您的运算符不是可结合的，您必须使用partial_sum，否则将是未定义的行为。

如果没有给出用户指定的运算符，我是否总是可以用inclusive_scan替换partial_sum？换句话说，将partial_sum(first, last, out)更改为inclusive_scan(first, last, out)是否安全?

通常，std::plus是可结合的（即，x + (y + z) == (x + y) + z将成立）。在这种情况下，更改是安全的。

但是有例外情况。一些奇怪的用户定义类可能以意想不到的方式重载std::plus。但是，浮点数操作是一个更有趣的例子，其在严格意义上不是结合的：

0.1 + (0.2 + 0.3) != (0.1 + 0.2) + 0.3
// could be identical on some architectures, but fails on my machine (x86-64, AMD FX-8370)

如果您的计算需要完全可重现，那么在将partial_sum更改为inclusive_scan时（与非顺序执行策略结合使用），必须牢记这一点。

然而，在实践中，浮点运算足够接近可以被认为是可结合的。如果操作的顺序不固定，甚至可以提高精度。也就是说，简单的顺序算法无论如何都不完美。

- Philipp Claßen

Answer 3

几乎一样，但是包容性扫描可以并行运行。同样的接口。

- gordazo0