14 分头行动并行搜索（第3/3页）

警用算法导论：并行算法

节选自Drecker教授讲义

并行算法所做的，是将一个问题分成数个小块，并同时在这些小块上执行计算，最后再将结果组合起来。由于将这些计算任务分给了不同的人同时执行，所以相比只有一个人来执行，并行算法可以更快地完成计算。考虑一个例子：我们在一幢废弃建筑中寻找逃犯，这种情况下能调动的警官越多，能同时搜索的房间就越多，因而也就能更快地找到逃犯。如果有30间房和30个警官，他们便可以在同一时间搜索所有的房间。

想要设计一个高效的并行算法，有两点很重要：第一是如何高效地将计算任务分割成互相独立的单元，第二是如何在最后将结果组合起来。有些问题并行起来非常容易，比如，你想在一大堆书卷中找一个线索，就可以很容易地将这些书卷分成数小堆，并让每个人负责找其中的一小堆。

然而相比之下，有些算法就很难甚至无法来并行计算。例如，要审问一个犯罪嫌疑人，即使有100个警官，审问的速度也无法加快。这个问题从根本上讲就是需要一步一步来的：你的下一个问题取决于犯罪嫌疑人对上一个问题的答案。而且更重要的是，犯罪嫌疑人同时只能回答一个问题。我曾经见过八个警官同时对一个犯罪嫌疑人大喊大叫，然而这并没有让审问的进度有任何加快。

当你考虑是否应该使用并行计算时，另一个需要考虑的方面便是，并行计算带来的效率提升是否大于它所带来的额外工作量。进行并行计算时，你需要额外地去分割问题和组合最后的答案。同时，给每个人布置任务也需要花费一定的时间。比如，在搜索一个只有三个元素的乱序数组时，如果你试图用并行计算，在你分割和布置任务的这段时间里，一个人早就可以把整个数组找完许多次了。