并行二进制搜索

Question

我刚刚开始学习并行编程,我正在研究二进制搜索.

通过投入更多的处理器,这无法真正优化吗？我知道这应该是分裂和征服,但你真的"正在减少和征服"(来自维基百科).

或者你可以将这些比较并行化吗？(如果X是小于array[mid],从搜索low到mid - 1;否则,如果X是大于array[mid]从搜索mid + 1到high,否则返回mid,的指数X)

或者你将一半的数组放到一个处理器上进行二进制搜索,另一半到另一个处理器怎么样？这不是浪费吗？因为它正在减少和征服而不是简单地分裂和征服？思考？

Answer 1

您可以轻松使用并行性.

对于k小于n处理器,分割成阵列n/k组和一个处理器分配给每个组.

在该组上运行二进制搜索.

现在时间是log(n/k).

还有一个船员方法是logn/log(k + 1).

Answer 2

我认为它肯定有资格进行并行化。至少跨越两个线程。让一个线程进行深度优先搜索，而另一个进行广度优先搜索。赢家是执行速度最快的算法，这可能因数据集而异。

Answer 3

我在并行编程方面没有太多经验，但我怀疑这是否适合并行处理。该算法的每一步都取决于执行一次比较，然后根据该比较沿着设定的“路径”前进（您要么找到您的值，要么现在必须根据比较在设定的“方向”上继续搜索）。两个单独的线程执行相同的比较不会让你更快地到达任何地方，并且单独的线程都需要依赖相同的比较来决定下一步做什么，因此它们不能真正自己做任何有用的、分开的工作。

至于您分割数组的想法，我认为您在这种情况下只是否定了二分搜索的好处。您的值（假设它在数组中）将位于数组的上半部分或下半部分。二分搜索中的第一个比较（在中点）将告诉您应该查看哪一半。如果您更进一步，请考虑将 N 个元素的数组分解为 N 个不同的二分搜索（这是并行的天真的尝试） - 尺寸）。当你不需要的时候，你现在正在进行 N 次比较。您正在失去二分搜索的功能，因为每次比较都会将搜索范围缩小到适当的子集。

希望有帮助。欢迎评论。