这篇关于C++14的N3554 (并行算法库)建议中,提出了当前std::partial_sum
的并行版本等内容。
template<
class ExecutionPolicy,
class InputIterator,
class OutputIterator,
class BinaryOperation>
OutputIterator inclusive_scan(
ExecutionPolicy &&exec,
InputIterator first,
InputIterator last,
OutputIterator result,
BinaryOperation binary_op);
带解释:
作用:对于范围 [result,result + (last - first)) 中的每个迭代器 i,执行 *i = prefix_sum, 其中 prefix_sum 是对应 sum init + *iter_0 + *iter_1 + *iter_2 + ... 或 binary_op(init, binary_op(*iter_0, binary_op(*iter_1, binary_op(*iter_2, ...))) 的结果,其中迭代器 iter_j 在范围 [first,first + (i - result) - 1) 中。求和的操作数顺序未指定。
这个操作怎么才能并行化呢?似乎按照定义,每个输出的前缀和都必须在计算下一个之前计算 - 实际上导致了串行操作。
编辑 非常感谢Aasmund Eldhuset的回答。个人认为,Guy E. Blelloch的"前缀和及其应用"非常有用。