讀古今文學網 > 算法神探:一部谷歌首席工程師寫的CS小說 > 14 分頭行動並行搜索 >

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個警官,審問的速度也無法加快。這個問題從根本上講就是需要一步一步來的:你的下一個問題取決於犯罪嫌疑人對上一個問題的答案。而且更重要的是,犯罪嫌疑人同時只能回答一個問題。我曾經見過八個警官同時對一個犯罪嫌疑人大喊大叫,然而這並沒有讓審問的進度有任何加快。

當你考慮是否應該使用並行計算時,另一個需要考慮的方面便是,並行計算帶來的效率提升是否大於它所帶來的額外工作量。進行並行計算時,你需要額外地去分割問題和組合最後的答案。同時,給每個人佈置任務也需要花費一定的時間。比如,在搜索一個只有三個元素的亂序數組時,如果你試圖用並行計算,在你分割和佈置任務的這段時間裡,一個人早就可以把整個數組找完許多次了。