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

Socks什么都没说。Frank又说道：“你想要干什么，Socks？”

“额……我对我们现在的搜索有些问题。”Socks回答道。

“什么问题？”Frank说道。

正如Frank担心的那样，Socks走了过来，坐在了他身边。

“你觉得我们会找到罪犯吗？”Socks问道。

Frank耸了耸肩说：“我们还有很多好线索。”

“不过你觉得我们来得及吗？”Socks问道。

Frank顿时警觉了。他转身狠狠地盯着Socks问道：“什么叫‘来得及’？”

Socks身子几乎向后倒了下去。他的眼睛不停地转着，似乎在寻找一个合适的答案。“就是赶在他们的计划之前抓住他们啊。”他最终说道。

Frank并没有就此罢休。“你还知道些什么？”他问道。

“没了，”Socks回复道，“至少，没有什么具体的东西了。都只是猜测，而且不是我的，而是我导师Gretchen的。不过她对这种事的直觉很准的。”

“什么叫‘这种事’？”

“我真的什么都不该说了。都只是猜测。”

“什么叫‘这种事’？”Frank低吼了一声。

“她认为这件事的幕后者准备在几天后攻击城堡。”

Frank跳了起来，叫道：“你怎么不早点说？”

“这只是猜测。”Socks重复道。

“那也不是瞎猜的。她一定有这样猜测的原因，”Frank说道，“不是吗？”

“嗯，不是完全瞎猜的，”Socks说道，“这是基于被偷的那个面具猜测的。这些魔法神器在满月的时候力量最强，而两天后就是满月了。”

“所以这个面具到底是干什么的？”Frank问道。他开始焦急地四处踱步了。

Socks犹豫了一下，说道：“这是一个力量非常强大的器物，”当他意识到Frank目光中的愤怒后，他加快了语速，“它的学名是外表组合面具。它在几百年前的Great SlugWar中丢失了。大家都以为它就这样遗失了，直到Ann公主在一次出征的途中找到了它。她是在……”

“所以它是干什么用的？”Frank不耐烦地问道。

“它可以让戴上它的人看起来像另外一个人。学者们认为它使用了一个巨大的并行搜索。它会对每一个面部特征都进行一次搜索。戴上它之后，你的鼻子会变成你想变成的人的鼻子那样，眼睛会……”

“一个完美的伪装？”Frank说道。

“对！”Socks赞同道。

Frank咒骂了一声，问道：“那城堡呢？为什么Gretchen认为他们会攻击城堡？”

“她没有说，”Socks承认道，“也许那部分的确是她猜的。”他补充道。不过显然他并不相信自己所说的。

Frank也并不相信。

“很抱歉之前没有提过这事，”Socks说道，“是因为没有任何证据……”他看起来痛苦极了。

“还有什么你没有告诉我的？”Frank盯着Socks问道。

Socks想了很久，回答道：“没有了。”

“全都告诉我了？”

“我知道的全都告诉你了。”Socks谨慎地说道。

Frank深吸了一口气，抬头看了看船帆。他多希望此时船能走得更快一些。过去一小时里，风几乎停了。现在的TCP Flyer号几乎是一步一步地爬向他们的目的地。

Frank在头脑中规划了一下他们接下来几天的时间安排。他不知道他们还有没有足够的时间。即使是三个人分头行动，也不一定能追查出足够多的东西。更糟的是，在TCP Flyer号靠岸以前，他们根本没有办法开始并行搜索。现在，他们能做的只是乖乖待在这艘船上而已。

警用算法导论：并行算法

节选自Drecker教授讲义

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

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

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

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