讀古今文學網 > 算法神探:一部谷歌首席工程師寫的CS小說 > 3 罪犯農場裡的數組和索引 >

3 罪犯農場裡的數組和索引

Frank看到一匹警隊的馬正拴在Crannock先生的房子外,不禁大聲爆了一句粗口。既然警長已經親自上門來雇他了,怎麼還會碰到其他的警官?如果警長不信任自己的警官們,或者是他們遭到了懷疑,警長就會把他們委派到城市邊遠地帶去調查一些小案子。如果他們只是單純的能力低下,也會落得同樣的下場。但是,從現在的情況看,有人已經在調查這個案子,而且Frank已經落後了。

Frank從虛掩著的前門溜了進去,到門廳去聽那位來調查的女警官和Crannock先生的談話。Crannock先生厭惡地瞥了Frank一眼,不過Frank的出現似乎早在他預料之中。但是,那位女警官看起來倒有些措手不及。

「你是誰?」她拿著羊皮紙和羽毛筆轉向Frank問道。

Frank懶得理她。「Crannock先生,」他說,「再次見到你很高興。」

「你又來煩我們了,是嗎?」Crannock說,「這裡可不歡迎你。」

「我才沒指望你們歡迎我,」Frank答,「我是來找你妻子的,想問她幾個小問題。」

那位女警官打量著他。「Frank?」她問,「Frank Runtime先生?前警探改行做私家偵探了?你在這做什麼?誰的寵物龍走丟了嗎?」她嘲笑道。

Frank還是沒搭理她,說道:「Crannock先生,您的妻子究竟在哪?」

那個老男人舉起了雙手:「她啥都沒幹!她已經金盆洗手了,這次是真的。」這一幕演得算得上是業餘演員了。

Frank笑了,他知道這話問得很令人不安,Crannock一定畏縮了。

「我知道,Crannock先生,我是來向她請教專業知識的。要不我請這位警官接著和你聊……」

「我是Notation警官。」那位年輕的女警官插嘴道,「我正在查案。」

她在撒謊,因為警官們永遠都是和搭檔一起調查案子的。更重要的是,Frank突然注意到她警徽上的名字是警長給他的執勤人員名單之中的一個,也就是說案發當晚,她也在警局值班。

「Notation警官,」Frank說,「誰說我是來查案的了?說不定我只是來找一條走丟的龍呢!」

她皺了皺眉頭。

屋後傳來了一陣騷動,有人在叫Crannock,不過被一聲響亮的馬叫聲打斷了。「我的妻子正和那些馬待在一塊,」Crannock先生不耐煩地說,「行了,她在2號穀倉,快去吧,別再賴在我的房子裡了!」Crannock把他們往前門趕,然後從後門急匆匆地跑了。

「謝謝你!」Frank轉身離開的時候喊道,「Crannock先生,見到您總是很愉快!」

Notation警官跟著Frank穿過了小花園,她很生氣,每一步都重重地跺著地面,問道:「你知道你在往哪走嗎?」

「2號穀倉啊。」Frank回答。

「我當然知道,」她咆哮道,「但2號穀倉在哪啊?」

Frank停下來轉向她問道:「你是剛從警校畢業嗎?Notation警官?」

「什麼?」

「這樣的搜索問題,只有菜鳥才會問。你沒有上過警務程序課和數據結構課嗎?或者是他們已經把這些課換成了小海龜畫圖這樣不嚴謹規範的課程了?」

Notation愣了愣,說道:「我當然上過那些課啊,」她聽起來有些底氣不足,「但我的意思是……」

Frank打斷了她:「那你就應該知道數組和索引。」

「是的,不過……」Notation說。

「在一個農場上找一個穀倉是一個再簡單不過的搜索任務了,」Frank又打斷了她,「我們可以用窮舉的方法去搜索每一個建築物。對農場上的每一個建築都要檢查一下是否為2號穀倉。在我上警校的那個年代,這是我們警用算法課第一節的內容。

「但是我們現在可以做得更好。Crannock一家把六個穀倉排在了一條整齊的線上,就像是一個巨型數組。Crannock先生非常好心地為我們寫好了穀倉的編號,也就是數組的索引,我們現在只需要走到對應的穀倉就行了。」

「我不是想問這個!」Notation揮動著手臂大聲吼道,「我知道怎麼用數組裡的索引,我也知道我們只用走到2號穀倉就好了,我畢業時在數據結構課和警用算法課上都拿到了第一,所以我不需要你在這給我說教如何正確使用數組。」

「剛剛是你自己問的啊。」Frank回答道。

「我問的是:你知不知道這個美麗可愛的穀倉數組在哪裡?」

「哦,原來你問的是這個啊,」他開始繼續向前走,說道,「雖然你說你是第一名,但看起來仍像一個菜鳥。」

「穀倉到底在哪?」Notation又一次吼著,仍然踩著重重的步伐趕上Frank。

Frank回頭對她一笑:「這座小山上。」

他幾年前得知,Crannock一家在生活中總是熱愛運用數組的思想,近乎瘋狂。他們會把所有的事物整理成井井有條的線性結構,然後將每個數組中的元素都標上清晰的索引。當Frank走過0號穀倉時,他看到了15個豬槽,每個豬槽可以放一份食物,農場裡的餵豬人沿著豬槽擺放的直線,用勺子將豬食一份一份地送到這個數組的對應位置上。

Frank和Notation走到了2號穀倉,穀倉門口有個牌子標記著一個大大的「2」。相比之前遇到的人的態度,Crannock太太有些高冷的問候已經很令人欣慰了,至少她沒有向他們砸任何東西……至少現在還沒有。

「你們想幹什麼?」Crannock太太問。

「Crannock太太,」Notation擔心Frank搶走了她的目擊證人,搶先問道,「我能不能問你幾個問題?」

Frank決定讓Notation先問。Billy提供的線索只能指引他找到這個農場,但是Notation看起來收集了更多的信息。

Crannock太太冷笑一聲,朝地上吐了口唾沫說道:「我啥都沒幹,我已經金盆洗手了。」

「我不是來逮捕你的,」Notation說,「我想問你一些關於驢車——Array Cart(數組車)的問題。」

Frank心裡閃過一絲疑惑。Notation難道是為了調查另一個案子才來這裡的嗎?他有些懷疑。直覺告訴他這個女人是為了那些丟失的文件而來的,而且他很相信自己的直覺。

「Array Cart啊,」Crannock太太說道,雖然她表面上是毫不遮掩的傲慢,但是語氣裡還是夾雜著疑慮,「這是我的發明,基於數組的原理而創造的。它有很多分開的棚,用來存放我的動物們。每一個棚只能存放一隻動物。我可以直接把某一隻動物放出來或者關進去,因為每個棚都有一扇門。這樣可以直接地訪問每一個存儲位置,既方便又節約時間。」

「這方法確實很巧妙,」Notation承認道,「你把數組和索引的概念運用在了牲畜的轉移上。」

「這只是一個開始,」Crannock太太補充說,「我和一個巫師在研究一種新型Array Cart,新型的Array Cart上帶有魔法指針!我敢打賭它們作為警隊的裝備是再好不過的了。跟你的警長說我可以給他一點折扣。」

Frank不得不讚揚Notation的機智,一旦說到數組,Crannock家的人就開始喋喋不休了。

「你現在是不是租出去了幾輛Array Cart?」Notation試探道。

Crannock太太突然變得極其冷漠地說:「我們做的事沒有違法,我們交了稅。」

Frank差點笑出聲,但還是忍住了。

「兩天前的晚上你是不是恰好把某些Array Cart租給了別人?」Notation步步緊逼地問道,「一種小一點的只有六個棚的Array Cart?」

「有可能吧。」Crannock太太說。她冷漠的舉止漸漸轉變為敵意。

Notation問:「你有記錄是租給誰了嗎?」

「沒,」Crannock太太說,「一旦借的人把Array Cart還回來,我就會把記錄撕掉,我現在也想不起來誰借的那一輛了。」

Billy的暗示似乎已經得到了驗證。一個想逃跑的罪犯能租到Array Cart的地方不多,租完Array Cart就被忘記更是不太可能,Crannock太太雖說自己已經金盆洗手,但她很明顯地在向從前的同夥提供非常有價值的幫助。

「你確定你一點都不記得之前的客戶了嗎?」Notation不罷休地問道,但是Frank知道這個問題是沒有意義的。他曾經為了一頭被偷的犛牛而問過她三個小時,儘管她是被偷的一方,但她還是沒有告訴他任何信息。Crannock太太不願意開口。

Notation在嘗試幾種不同的問法,希望套出一點話,這時Frank悄悄地從穀倉溜了出去,找到了Array Cart的停車場。

不出他所料,停車場的十個車位被整理成了標過號碼的數組,只有2號、4號和8號車位停著Array Cart。不過2號和4號的車位上停的都是有10個棚的Array Cart,都不是Notation說的那種。8號車位上停的才是有6個棚的Array Cart,它的輪子上還留著沒完全干的泥土。

Frank掃視了周圍,跳進這個有六個棚的Array Cart上。Array Cart的地板上零散地鋪著稻草,但沒有牲畜。Frank逐一打開每一個棚的門,在空無一物的空間裡尋找線索。他趴在地上,一層層撥開稻草,直到找到了一些羊皮紙的碎片。

Frank一共找到了六片,可能是在把文件搬下Array Cart時被釘子割下來的邊邊角角。其中只有兩片有文字,看起來像是賬目的一部分。雖然這不是什麼可靠的線索,但這能表示這輛Array Cart和案子脫不了干係。

Frank開始檢查Array Cart的前面,小心地在駕駛座找線索。他在椅子那裡找到了第一條真正的線索——在木椅子殘破的地方,卡著幾根黑色和橙色的細線,是披風上的線。Frank斷定這件披風一定是新的,因為細線還沒褪色。他心滿意足地把細線裝在口袋裡,從Array Cart上跳下來。

當呼吸到一口新鮮空氣時他才意識到,原來自己一直是屏住呼吸的。Array Cart的周圍瀰漫著魚腐爛後的腥臭味。他嗅了嗅,循著臭氣找到了根源——被泥土蓋住的輪子。他深吸了一口氣,但是立馬就後悔了,那些泥土散發出的鰻魚腐臭的氣味是如此噁心。

Frank一邊微笑一邊作嘔地遠離了這輛Array Cart,因為雖然他不知道是誰租了這輛Array Cart,但他毫無疑問地知道了這輛Array Cart曾經去過哪裡。

警用算法導論:數組

節選自Drecker教授講義

數組是可以讓你存儲多個值的簡單數據結構。一個數組就像一排箱子一樣,每個箱子可以存儲一條信息,例如一個數或一個字符。

數組結構的意義在於,可以通過指定一個位置或索引的方法來存儲或讀取數組中的任何值(或元素)。很多編程語言數組的索引都是從0開始的。這也就意味著第1個值存放在第0位,第2個值存放在第1位,以此類推。通常數組A中索引為i的值存儲在A[i]中。例如,上面的數組A的第3個元素的索引為2,我們用A[2]表示,存儲的值為19。

昨天警校組織大家參觀監獄時你可能已經發現了這個結構的運用。國王親自建議使用索引來對牢房進行編號,這樣可以簡化對犯人的檢索。現在每個警局都根據當地犯人的人數配備了4~8個編過號的數組牢房來關押犯人。