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国家文件:

换句话说,可以以任意顺序执行求和操作.如果binary_op不是关联的,则行为是不确定的.

std::partial_sum没有任何保留的国家文件:

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

因此,std::inclusive_scan等效于std::partial_sum仅当binary_op是缔合,即,当(a运算b)的运算c = a的运算(b运算c).

在非关联的情况下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 );

对于像整数这样的许多类型， wherestd::plus是关联的，partial_sum并且inclusive_scan是相同的。后面的算法是一样的，其实“包含扫描”、“部分求和”等都是同一种计算的同义词（维基百科称之为前缀求和）。

但是在采用用户指定运算符的其他重载中存在差异：

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，否则，它将是未定义的行为。

如果没有用户指定的运营商给出，可我总是代替partial_sum与inclusive_scan？换句话说，是安全的改变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（结合非顺序执行策略）时必须牢记这一点。

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