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 );

谁能详细说说他们的区别？我什么时候会选择一个而不是另一个？

Answer 1

std::inclusive_scan 的文档说明：

In other words, the summation operations may be performed in arbitrary order. The behavior is nondeterministic if binary_op is not associative.

std::partial_sum 的文档毫无保留地指出：

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

因此，只有当 binary_op 是关联的，即 (aop[= 时，std::inclusive_scan 才等同于 std::partial_sum 18=]opc = aop(bopc).

在非关联 binary_op 的情况下，std::partial_sum 将产生确定性结果，而您不知道 std::inclusive_scan.

会发生什么

Answer 2

std::inclusive_scan 作为并行 STD 的一部分添加到 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"等都是同一种计算类型的同义词（维基百科称之为prefix 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 );

When would I choose one over the other?

如果您的运算符是关联运算符，我建议始终使用 inclusive_scan。即使您将始终使用顺序执行，它也可以作为某种形式的文档。
如果你知道你的运算符不是关联的，你必须使用partial_sum，否则将是未定义的行为。

If no user-specified operator is given, can I always replace partial_sum with inclusive_scan? In other words, is it safe to change partial_sum(first, last, out) to inclusive_scan(first, last, out)?

通常，std::plus 是关联的（即，x + (y + z) == (x + y) + z 将成立）。那样的话，改一下就安全了。

不过也有例外。一些奇怪的用户定义类可能会以意想不到的方式重载 std::plus。但更有趣的情况是浮点运算，即 not associative in a strict sense:

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（结合非顺序执行策略）时必须牢记这一点。

不过，在实践中，浮点运算足够接近以被认为是关联的。如果操作顺序不固定，甚至可以提高准确性。这意味着，简单的顺序算法无论如何都不是完美的。

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

What's the difference between std::partial_sum and std::inclusive_scan?

c++

numeric

stl-algorithm

c++17