我有这个数组（A）有n个元素保证排序，我需要在并行系统中对它们执行二进制搜索 . 我开始制作这种二进制搜索算法 . 这是迭代的，因为我还不确定如何将递归合并到并行处理中 .
/* Looking for element k in array A of length n */
min = 0;
max = n - 1;
while(min <= max)
{
midpoint = min + ((max-min)/2); //index
if(A[midpoint] > k) //discard upper half
max = midpoint - 1;
else if(A[midpoint] < k) //discard lower half
min = midpoint + 1;
else
return midpoint; //Found k, return index
}
return -1; //not found
在并行算法中，我可以访问p个处理器，它是一个允许并发读取但是独占写入的系统 . 真正的问题是我还在继续思考 . 也就是说，我似乎无法看到任何方式可以通过多个处理器来完成，因为你不能“丢弃”数组中不需要的部分，而不必先知道你在中点值方面的位置 . 它看似天生顺序 .
伪代码：
Global: //Variables accessible by all processors
index; //index of k
p; //number of processors
i; //the i^th processor
n; //number elements in array A
A[0, 1, ... , (n-1)];
local: //Variables accessible by only the owning processor
//Not sure what I need yet
Begin
Spawn(P1, P2 . . . P(p-1)); //"create" the p processors
for all P where 0 <= i <= (p-1) do //each processor does the following code
//I'm stuck here
endfor
End
最后一件事：我看到一个用户发出的问题，询问是否有办法用并行处理进行二进制搜索 . 这个问题没有真正决定性的答案，因为这两个相关的答案都得到了1票 . 有人说它实际上是不可能的，因为它是一步一步的过程，而另一个人似乎非常有信心它真的很容易实现 . 你的想法是什么？
2 回答
虽然技术上可以并行运行二进制搜索，但我不建议这样做 .
并行运行的最佳算法是那些具有可以同时运行的彼此分离的离散元素的算法 . 例如，将3d图形渲染成视频是好的，因为每个帧是独立的并且可以被给予单独的处理器 .
您可以将树划分为多个段，以便每个处理器都可以处理，但考虑到二进制搜索的性质，只有众多处理器中的一个会找到答案因此浪费了所有其他处理器的计算工作量 . 在他们的细分中有搜索元素 . 这甚至没有考虑到线程的开销 .
现在，如果另一方面，您在一个二叉树上进行了一系列搜索，这将是另一回事 . 您可以拥有一个所有线程都来自的作业队列，执行二进制搜索并进行响应 . 这样，您可以并行运行多个搜索，而不是搜索的一部分 . 如果您希望进一步优化它，您还可以实现缓存 .
简而言之，不要试图在处理器之间拆分单独的二进制搜索，因为除了浪费处理器时间之外你不会获得任何东西 . 但是，如果您正在进行许多搜索，则可以通过并行运行多个搜索来获得 .
与并行解决的所有问题一样......这在很大程度上取决于数据的大小，消息/共享内存的速度以及您的要求 .
写锁的速度有多快，同步速度有多快？如果它们足够快（例如，在一台机器上使用共享内存）并且您的数据大小足够大，则可以使用特定类型的“拆分和运行”技术 . 您可以将其想象如下：
二进制搜索是一种分而治之的方法，您可以在每次迭代后更新您正在检查的范围 - 每次迭代时范围减半 . 不是将当前范围分成2，而是将其分成
p个部分，其中每个进程负责其中一个部分;在每次迭代中，“获胜”片段（在其范围内具有目标值的片段）将要搜索的新范围写入内存，并在开始下一次迭代之前同步这些过程 . 如果您有足够的数据，那么从每次减半数据到减少数据每次都可能是一场胜利 . 您将从$ O（log_2（x））$转到$ O（log_p（x））$ .这种方法只有在写入和同步足够快时才有效，因为它依赖于大量的写入和同步 . 如果您在群集中执行此操作，则这些会变得昂贵 . 如果进程之间的通信很困难，那么您可以做的最好的事情就是在链接到的其他帖子中建议的“拆分和运行” . 具体来说，获取已排序列表的每个
p元素，并将其放在不同的节点上 . 然后，当请求进入时，在所有节点上进行二进制搜索 . 如果数组中的值是唯一的，则只有一个节点会找到答案，并且该节点可以返回结果 . 这是一个相对较差的并行性，因为你重复了很多工作 - 你忽略了之间存在的顺序不同节点上的数组 . 但它会为你提供从$ O（log_2（x））$到$ O（log_2（x / p））$的加速 .实际上，很难知道哪种方法可以提前在您的硬件上运行良好 . 通常，您必须在确保所有进程始终处于活动状态并确保不会损失太多通信开销时间之间取得经验 balancer .