首页 » 算法神探:一部谷歌首席工程师写的CS小说 » 算法神探:一部谷歌首席工程师写的CS小说全文在线阅读

《算法神探:一部谷歌首席工程师写的CS小说》14 分头行动并行搜索

关灯直达底部

“发生什么了?”Notation警官站在门边问道。Frank一边喘了口气,一边打量着她,心里想:她是在担心呢?还是在疑惑呢?

“我们被袭击了!”Socks脱口而出,“我们被困在了一间小房间内。房间内所有的东西都烧起来了!幸亏我使用了弱化铁的咒语,我们才得以逃脱。”他看起来对自己的表现挺得意的。

“袭击?”Notation问道,“谁袭击了你们?你们看到他们了吗?他们长什么样?”

“没有,”Socks承认道,“他从后面袭击了我。”

“Frank你呢?”Notation转向Frank问道。

Frank摇了摇头:“我只看到Socks向我冲来。”

“我觉得他的个子一定很大,”Socks说道,“一个巨大的恶棍。他身手敏捷且隐蔽,也许是一个受过训练的杀手。”

Frank转了转眼珠,说道:“不好意思,年轻人。他肯定是一个新手。专业的杀手不会把人关在房间里就逃走。”

“但是那大火呢?”Socks问道。

“是你的魔杖引起的火,”Frank提醒道,“你把它掉在那堆纸上面了。”

“纸?”Notation问道,“你们找到那些日志了吗?知道他们是在找什么了吗?”

Frank和Socks对视了一眼。Notation的眼神游走在他们之间。终于,Frank开口了:“那些日志都没了。我们这位初级巫师把他的魔杖掉在了纸堆上,然后大火就烧得到处都是了。所有线索现在都没了。”

Socks瞬间脸红了,两眼盯着地面。

“没了?”Notation问道,“所有线索都没了?你确定吗?”

“对。”Frank面向门内飘出的黑烟点头道。

“那袭击你们的那个人呢?”Notation问道。

“我没有看到他,”Frank说道,“我觉得你也什么都没看到,是吧?”他问Notation道。这样的问法比他原本打算的问法要尖锐许多。不过,他刚从一个燃烧的房间中逃出来,此时并没有什么心情来绕圈子。

“没有,”Notation冷静地回答道,“我在前面这里什么都没有看到。”

“门旁边也什么都没有?”Frank问道,“任何可能帮我们找到袭击者的线索都没有?”

Notation摇了摇头。“什么都没有,”她说道,“不过我看了看另一边,那里感觉好几个月都没有人去过了。”

Frank点了点头,但什么都没说。他感觉有些蹊跷,要么袭击者巧妙地避开了站在前门这里的Notation,要么就是Notation在隐瞒什么。她之前离开过多久?为什么她一直都不进去?Frank觉得现在不要刨根问底了,便说道:“好吧。让我们回到船上吧。”

“现在怎么办?”当他们走回水边的时候,Socks问道。

“该倒退了,”Frank说道,“这儿没有更多的线索了。”

“倒退到哪里?”

“去追查其他的线索,”Frank回答道,“我们应该去调查剩下的线索。”他停了一会,思索着他的选择,说道:“我想我们是时候开始使用并行搜索了。”

“你确定吗?”Notation问道。

“并行?”Socks问道。

“并行就是说我们分头去追查搜索空间的不同部分,”Notation回答道,“并行算法把要做的工作分成几份,然后同时执行它们(比如把它们分给多个人同时去做)。现在,我们可以把所有的线索分成三类。你、Frank和我可以每人去追查一类线索。这样我们可以同时追查多个线索,让我们的效率提升两倍。”

“但是,”Socks反对道,“我不是警官,也不是私家侦探。我不知道该做什么啊。难道我不应该跟着你们中的一个人吗?”

“不,”Frank说道,“虽然我还不知道我们面临的是什么,但我感觉我们的时间不多了。无论我们追查的人是谁,他已经知道我们在调查他了,也知道我们已经追查到这儿了。如果他们还算聪明的话,就会马上开始销毁剩下的证据了。”

“但等到我们回到Usb港时天色就会很晚了。”Socks说道。

“我们可以今晚分头行动,明早在我办公室会合,”Frank说道,“这样我们应该有足够的时间去追查线索,或许还能睡一觉。”

“好,”Notation同意道,“那我们怎么来划分工作呢?”

Frank知道在一个高效的并行算法中很重要的一点便是工作的划分方式,需要保证多个人同时工作所能带来的效率提升高于划分工作所需要的代价。并行处理会带来一定的额外代价:问题需要被划分成很多部分,每个人需要拿到自己的那一份,并且最后所有人的结果还需要被合并起来。正是因为这些代价,对于一些简单的问题,有时并行处理还不如直接让一个人做。不过,当问题规模变得足够大的时候,并行处理可以很大程度上加速一个算法。

“太简单了,”Frank说道,“Socks,我需要你向你的巫师朋友们打听关于那个联盟的消息。船上的恶棍说过他们是在为一个联盟工作。不过他们还没说完就被Rebecca Vinettee打断了。从之前案子的经验来看,这个联盟的真名应该会很邪恶,比如叫‘黑暗联盟’或者‘嗜权利狂人联盟’这种。这种邪恶的联盟一般在名字上也不会藏着掖着。找到你能找到的所有关于这个组织的信息。”

“这线索也太希望渺茫了。”Socks抱怨道。

“Notation,”Frank继续道,“我需要你找出过去六个月所有警察调职的记录。”虽然他并不是很想把这个任务交给Notation,但她是唯一可以轻易拿到这些记录的人。如果Frank试图自己去找这些记录,别人一定会以怀疑的眼神看着他。再说了,如果他去做的话,首都警察局的人肯定会让他填写一大堆各式各样的表格。这些人简直把表格用得和路障一样了。

“调职?”Notation问道,明显很惊讶,“为什么?”

“就当是我的直觉吧,”Frank撒了一个谎,“我们明早在我的办公室会合,分享我们找到的信息。”

“那你呢?”Notation问道,语气有些恼怒。很明显,她意识到了Frank对她有所隐瞒。

Frank对她无辜地笑了笑,说道:“我需要去买些东西。”

在TCP Flyer号缓慢地驶向Usb港的过程中,Frank找了个没人的角落,坐下来开始思考。这种丢失重要线索的感觉总会让Frank十分害怕——害怕他晚对手一步。Frank强行将这些疑虑从脑中消除,重新开始思考剩余的线索。回程的这段时间足够让他来重新归纳整理所有的线索,以及想想他有没有漏掉什么了。

他闭上眼睛,深呼吸了一下。

“哦。对不起,你在睡觉吗?”Socks问道。

“不,我在思考。”Frank说道。他很惊讶自己居然没有对他吼叫。不管怎么说,这位巫师都算救了他的命。

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个警官,审问的速度也无法加快。这个问题从根本上讲就是需要一步一步来的:你的下一个问题取决于犯罪嫌疑人对上一个问题的答案。而且更重要的是,犯罪嫌疑人同时只能回答一个问题。我曾经见过八个警官同时对一个犯罪嫌疑人大喊大叫,然而这并没有让审问的进度有任何加快。

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