并行二分查找

Question

我刚开始学习并行编程，正在研究二分查找。

这个算法似乎不能通过增加处理器来优化，对吗？我知道它被称为“分而治之”，但实际上是“减而治之”（来自维基百科）。

或者你能否将比较过程并行化呢？（如果X小于array[mid]，则从low到mid-1搜索；如果X大于array[mid]，则从mid+1到high搜索；否则返回mid，即X的索引）

还有，你可以将数组的一半交给一个处理器进行二分查找，将另一半交给另一个处理器，不过这样做是否会浪费资源呢？因为它是“减而治之”，而不是简单的“分而治之”？你有什么想法？

- user114518

Answer 1

您可以轻松使用并行处理。

对于 k 小于 n 的处理器，将数组分成 n/k 组，并为每组分配一个处理器。

在该组上运行二分查找。

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

还有一种称为“乘务员方法”的方法，其时间复杂度为logn/log(k+1)。

- Orch

---

你能提供一个链接到船员方法吗？ - Thomas Ahle

请仔细考虑。在键不存在的桶的第一次迭代中会发生什么。 - alecco

这里有一篇关于Crew算法的好论文： https://www.cs.umd.edu/~gasarch/TOPICS/ramsey/parasearch.pdf - Orch

Answer 2

我认为这个算法肯定适合并行化处理。至少可以跨两个线程进行。一个线程执行深度优先搜索，另一个线程执行广度优先搜索。胜利者是表现最快的算法，这可能因数据集不同而异。

- Kaz Dragon

---

如果有读者认为我在轻率，那么实际上并非如此。在时间关键的部分，如果一个算法本身无法进行并行化，则使用具有不同性能特征的多个算法可能是一种有效的优化方法，以保持最坏情况下的大O符号不超出界限。 - Kaz Dragon

你如何将DFS或BFS应用于二分查找？ - Ari

@Ari 我猜你会将数组构建成二叉搜索树的结构。 - adnanmuttaleb

Answer 3

我在并行编程方面的经验不多，但我怀疑这并不是一个适合并行处理的好选择。算法的每一步都依赖于执行一次比较，然后根据此比较沿着一组“路径”继续进行（您要么找到了您的值，要么现在必须根据比较继续在一组“方向”中搜索）。两个执行相同比较的单独线程不会更快地帮助您，而且单独的线程都需要依赖于相同的比较来决定下一步该做什么，因此它们无法自行完成任何有用的分工。

至于您将数组拆分的想法，在这种情况下，我认为您只是否定了二分查找的好处。您的值（假设它在您的数组中）将在数组的上半部分或下半部分中的一个。二分搜索中的第一次比较（在中点处）将告诉您应该在哪个半部分中寻找。如果您进一步考虑将N个元素的数组拆分为N个不同的二分搜索（一种天真的尝试并行化），那么您现在正在进行N次比较，而实际上您不需要这样做。您正在失去二分搜索的优势，因为每次比较都将缩小您的搜索范围到适当的子集。

希望这有所帮助。欢迎评论。

- Bryan

Answer 4

在传统的并行化（多核）意义上，二分查找和BST并没有太大改进。

有一些技术，比如为每个处理器在L1缓存中拥有多个BST的副本。只有一个处理器是活动的，但是拥有多个L1缓存可以带来巨大的收益（L1需要4个周期，而L2需要14个周期）。

在实际问题中，您通常会同时搜索多个关键字。

现在，还有另一种可以帮助的并行化技术：SIMD！请查看来自Intel / UCSC / Oracle团队的“Fast architecture sensitive tree search on modern CPUs and GPUs”（SIGMOD 2010）论文。非常酷。顺便说一下，我正在基于这篇论文进行当前的研究项目。

- alecco

Answer 5

并行实现可以加速二分搜索，但改善并不特别显著。在最坏情况下，进行二分搜索所需的时间为log_2(n)，其中n是列表中元素的数量。一个简单的并行实现将主列表分成k个子列表，由并行线程进行二分搜索。这种二分搜索的最坏情况时间为log_2(n/k)，实现了理论上的搜索时间减少。

例子： 使用单个线程对包含1024个条目的列表进行二分搜索需要多达10个周期。使用4个线程，每个线程只需要8个周期即可完成搜索。而使用8个线程，则每个线程需要7个周期。因此，8个线程的并行二分搜索可能比单线程模型快高达30％。

然而，这种加速不应与效率提高混淆：相比于单线程的二分搜索执行的10次比较，8线程模型实际上执行了8 * 7 = 56次比较来完成该搜索。对于程序员来说，使用并行应用程序进行二分搜索的微小速度增益是否适合或有利于他们的应用程序，完全取决于他们的判断。

- whit

---

我应该补充说明，这是一个“减少和征服”的例子，而不是通常更理想的并行实现的“分而治之”。在这种情况下，每个线程执行的问题比原始搜索小，因此速度更快，但这些问题的总和大于原始问题。如果我们能够在这里管理“分而治之”的实现，较小问题的总和将与原始单线程实现相同，但速度会快k倍（其中k为并行线程数）。 - whit

提高30%的速度非常显著！ - Ari

Answer 6

我相信可以通过对二分搜索进行优化，将其加速因子提高到log（M），其中M是处理器的数量。当M是一个常数时，log(n/M) = log(n) - log(M) > log(n)/log(M)。虽然我没有紧密下限的证明，但如果M=n，则执行时间为O（1），这是无法再进一步优化的。下面是算法草图。

Parallel_Binary_Search(sorted_arraylist)

1. 将排序后的列表sorted_arraylist划分成大小为n/M的M个块。
2. 对每个块的中间元素进行一次比较。
3. 如果比较器表示相等，则返回地址并终止。
4. 否则，找到比较器分别标记(>)和(<)的相邻两个块。
5. 从标记(>)的元素后面一个元素开始，到标记(<)的元素前面一个元素结束，形成一个新的Chunk。
6. 如果它们是同一个元素，则返回失败并终止。
7. 否则，运行Parallel_Binary_Search(Chunk)。

- Aly Farahat