c++ - 待定:并行查找第一个元素

Question

我遇到了这个问题:

• 找到列表中满足给定条件的第一个元素。

不幸的是，列表很长(100.000 个元素)，使用一个线程评估每个元素的条件总共需要大约 30 秒。

有没有办法完全并行化这个问题？我查看了所有的 tbb 模式，但找不到任何合适的。

更新:出于性能原因，我想在找到某个项目时尽早停止并停止处理列表的其余部分。这就是为什么我认为我不能使用 parallel_while 或 parallel_do。

Answer 1

我对库不是很熟悉，但仔细想想，你能不能让一组线程从不同的角度以相同的步幅迭代不同？

假设您决定拥有 n线程(= 内核数或其他)，每个线程都应指定一个特定的起始点，直到 n , 所以第一个线程开始于 begin() , 它比较的下一项是 begin() + n等。第二个线程开始于 begin()+1然后它的下一个比较是在 n 中等等

这样你就可以让一组线程在列表中并行迭代，迭代本身可能并不昂贵——只是比较。不会对任何节点进行多次比较，并且您可以在任何线程进行匹配时设置一些条件，并且所有线程都应在迭代/比较之前检查此条件..

我认为实现起来非常简单(？)