并发二值斩波算法
有没有办法（或者理论上可能）同时实现二分搜索算法？我猜答案很可能是否定的，原因有两个：
- 尽管进行了大量的谷歌搜索，但我还没有在任何地方找到并发实现
- 二进制斩的每个迭代周期都取决于前一个迭代的值，所以即使每次迭代都是一个单独的线程必须阻塞，直到前一个线程完成，从而使其顺序执行。
但是，我想在这方面进行一些澄清（如果可能的话，有任何链接或示例吗？）
Is there a way (or is it even theoretically possible) to implement a binary search algorithm concurrently? I'm guessing the answer may well be no for two reasons:
- Despite lots of Googling I haven't found a concurrent implementation anywhere
- Each iterative cycle of the binary chop depends on the values from the previous one, so even if each iteration was a separate thread it would have to block until the previous one completed, making it sequential.
However, I'd like some clarification on this front (and if it is possible, any links or examples?)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
乍一看，二分查找似乎是完全不并行的。但请注意，只有三种可能的结果：
所以我们开始三个并行的过程：
一旦我们知道第一个元素的结果，我们就可以杀死那些不会找到该元素的元素。但与此同时，在正确位置进行搜索的过程使搜索速率加倍，即当前加速比为 3 中的 2。
当然，如果您拥有 3 个以上的核心可供使用，则可以推广此方法。重要的一点是，这种思维方式是在硬件内部完成的。例如，查找超前进位加法器。
At first, it looks like binary search is completely nonparallel. But notice that there are only three possible outcomes:
So we start three parallel processes:
As soon as we know the result from the first of these, we can kill the one which is not going to find the element. But at the same time, the process that searched in the right spot, has doubled the search rate, that is current speedup is 2 out of a possible 3.
Naturally, this approach can be generalized if you have more than 3 cores at your disposal. An important aside is that this way of thinking is what is done inside hardware. Look up carry-lookahead adders for instance.
我想你一定能找到答案！要并行化，必须有一些工作是可以划分的。在分箱搜索的情况下，没有任何东西可以被分割和并行化。 bin-search 进入值数组的中间。这项工作不能分割。等等..直到找到解决方案。
您认为什么可以并行化？
I think you can figure the answer! To parallelize, there must be some work that can be divided. In case of the bin-search, there is nothing that could possibly be divided and parallelized. bin-search gets into the middle of an array of values. This work cannot be divided. Etc.. until it find the solution.
What in your opinion could be parallelized?
如果您有 n 个工作线程，则可以将数组拆分为 n 个段并同时运行 n 个二分搜索，并在结果准备好时将其合并。除了这个廉价的技巧之外，我看不出有什么明显的方法可以引入并行性。
If you have n worker threads, you can split the array in n segments and run n binary searches concurrently, combining the results when they are ready. Apart from this cheap trick, I can see no obvious way to introduce parallelism.
您始终可以尝试不完全二元搜索，本质上，如果您有 n 个核心，那么您可以将数组拆分为 n+1 个部分。从那里您搜索每个“切点”并查看该值是否大于或小于切点，这会导致您拥有原始搜索空间的五分之一而不是一半，因为您将能够选择较小的部分。
You could always try a not-quite-binary search, essentially if you have n cores then you can split the array into n+1 pieces. From there you search each of the "cut-points" and see whether the value is larger or smaller than the cut point, this results in you having a fifth of the original search space as opposed to half, as you will be able to select a smaller section.