并行二进制搜索 [英] Parallel Binary Search

问题描述

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

这真的不能通过添加更多处理器来优化吗?我知道它应该是分而治之，但您实际上是在减少并征服"(摘自 Wikipedia ). /p>

还是可以并行比较? (如果X小于array[mid]，则从low搜索到mid - 1；否则，如果X大于array[mid]，则从mid + 1搜索到high，否则返回mid，则X)

的索引

或者您将数组的一半分配给一个处理器进行二进制搜索，而另一半分配给另一个处理器呢?那不是很浪费吗?因为它是减少和征服，而不是简单地划分和征服?有什么想法吗?

解决方案

您可以轻松地使用并行性.

对于k少于n个处理器的情况，请将阵列划分为n/k个组，并为每个组分配一个处理器.

对该组运行二进制搜索.

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

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

I'm just starting to learn about parallel programming, and I'm looking at binary search.

This can't really be optimized by throwing more processors at it right? I know it's supposedly dividing and conquering, but you're really "decreasing and conquering" (from Wikipedia).

Or could you possibly parallelize the comparisons? (if X is less than array[mid], search from low to mid - 1; else if X is greater than array[mid] search from mid + 1 to high, else return mid, the index of X)

Or how about you give half of the array to one processor to do binary search on, and the other half to another? Wouldn't that be wasteful though? Because it's decreasing and conquering rather than simply dividing and conquering? Thoughts?

解决方案

You can easily use parallelism.

For k is less than n processors, split the array into n/k groups and assign a processor to each group.

Run binary search on that group.

Now the time is log(n/k).

There is also a crew method that is logn/log(k+1).

这篇关于并行二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！