c++ - 与 ForwardIterator 的并行性？

Question

我只是在考虑我们是否可以加快提取出现在已排序 std::list<int> 中的不同元素的速度通过运行 parallelized version的 std::unique_copy() .

我的想法是这样的:

• 将数据分成几部分。
• 将算法并行应用于这些部分。
• 合并结果，同时计算各部分之间的边缘情况。

但正如我所见，只有一个 ForwardIterator 而不是 RandomAccessIterator，至少需要两遍才能并行解决这个问题:一次设置部分，下一次应用算法。

我明白，并不是每个问题都会受益于并行化的优点。

我对它的工作原理的理解是否正确(大约)？

那么我的问题是，为什么并行算法不需要 RandomAccessIterators？在这里支持 ForwardIterator 有好处吗？算法能否检测出它们拥有哪种类型的迭代器，并相应地选择更高效的版本？

Answer 1

并行算法支持前向迭代器的原因是并行化可以提高这些算法的性能。

是的，前向迭代器一次只能在受控序列中移动一步。但是算法不仅仅只是移动——您还必须查看算法所做的其他事情。

例如，如果复制一个对象的成本很高，使用前向迭代器的std::copy可以并行地更快，因为复制对象所需的时间决定了遍历时间；吐出并行拷贝提高了整体速度，即使前向迭代器意味着并行算法比串行算法做更多的工作。