(圖片來源:pixabay)
配對襪子
瑪姬‧沃納夫人是從前家世顯赫的一個維也納家族後代,最近卻因為偷偷挾帶健達出奇蛋到美國而遭起訴。目前她在伯恩這座城市裡寄宿幫工,而這也是她有生以來首次親手折疊衣服。瑪姬驚訝地發現,這個接待家庭裡的成員頻頻為了找到一雙成對的襪子而揮汗如雨,過程耗時簡直超乎她的想像。幸好這一家人的腳的大小和偏好的顏色各不相同。
建議:雖然這當中包含了若干任務,但也許我們可以從最根本的任務切入。
你是否想過「記憶」這一生物特性對人類有多麼不可或缺?某個人靠在椅背上,闔上雙眼、單手撫著額頭回想一節詩句或一組方程式,或一串電話號碼,這呈現出的樣貌就是典型的人類寫照。試著想像如同癡呆症患者經歷的每一天,缺乏記憶能力的生活會變得多麼艱難。首先,你可能得反覆做許多相同的事情,就像電影《記憶拼圖》(Memento)裡的主角那樣,每天起床睜開眼都得重新讀取所有必須完成的任務訊息。
我在一開始著墨於此的原因是想說明,解決問題的較快方法之所以會快,正巧就是運用了記憶力。去年擊敗了圍棋世界冠軍的人工智慧程式AlphaGo,便是因為具有向職業棋手學習及自學的能力,因而在關鍵技巧上累積了龐大記憶。換言之,我們會在本書裡介紹到許多解決問題的較快方法,雖然做法簡單,但卻較有效率的原因是,它們都具有避免在同一事物上反覆執行相同動作的特質。
還是別操之過急吧!讓我們回到襪子的問題,幫幫那位近來被沒收了巧克力,成為聯邦調查局黑名單的可憐瑪姬。她正面臨在堆積如山的衣物中,找出一雙雙成對襪子的艱鉅任務。我們先關注在此所包含數項任務的其中一項,並想出著手該任務的兩種可能方法。
在繼續閱讀之前,我會建議你拿出紙筆、道具或其他便利的物品來逐步理解這些場景情境。針對各個步驟和假設,動腦想想達成目標究竟需要哪些要素。在接下來的每一章節,都不妨試著這樣做吧!
假設衣物堆裡只有四雙襪子,那麼瑪姬不管使用哪種方法其實都差不多,而且想必可以迅速完成工作。但想像瑪姬此刻面對的是好幾百雙的襪子;如果她選用第一種方法,那麼她有很高的機率會反覆拿到同一隻襪子,因為她始終沒有把這隻襪子從衣物堆裡取出來。打從她第一次拿到那隻襪子,她就沒有從中擷取到任何訊息。然而,若採用第二種方法,她把尚未配對成功的襪子排列在一旁,因而避免了在衣物堆裡再次拿到同一隻襪子的可能性。
因此第二種方法由於依靠記憶,結果較為快速;更確切地說,是因為應用了所謂的查找表(lookup table)或快取記憶體(cache)。雖然未必需要,但你不妨將查找表視為一批獨特的識別碼(「鍵」﹝keys﹞),每一識別碼都指向資料的關聯項目(「值」﹝values﹞),而你就在此當中「查找」鍵值,這種表現形式又稱作鍵值對(key-value pair)。反觀我們的故事情境,「顏色」或許可以用來代表「鍵」。比方說,當瑪姬拿到一隻紅色的襪子時,她會在那一排尚未配對成功的襪子裡查找「紅色」。當她找到了「紅色」的區塊,她又會進一步去查找額外的識別碼,例如樣式、色調等,再以此作為完成配對任務的基礎。相反地,假如她沒有找到這一區塊,她就會用那隻孤零零的紅色襪子建立一個新的「紅色」類別。
兩種方法的對照,如圖所示。你發現了嗎?當衣物堆裡的襪子數量增加時,方法一的速度顯然比方法二緩慢許多。處理本書提及日常任務的方法還有很多種,當然不限於文中強調的兩種途徑,之所以特別討論的目的是為了突顯這兩種方法在漸近增長率(asymptotic rates of growth)上存在顯著差異,因而省略了執行結果可能落在兩者之間的其他方法。舉例來說,瑪姬也可藉由鴿籠原理(pigeonhole principle),也就是從衣物堆裡一次拿取六隻襪子的方式來完成配對任務。
當我們從衣物堆裡拿到某隻襪子時,我們或許可以很快辨認出是否曾見過成雙的另外一隻。大部分人的短期記憶都能不費吹灰之力記住大約六組事物,而這剛好就能在此情境中派上用場。因此當你在衣物堆裡看到和先前放在一旁的相同襪子時,你應該能產生出「哈!這我剛才有看到!」的立即反應。假如你有玩過記憶翻牌的遊戲,你對這種記憶能力發揮的功效和限度應該不陌生。
如果襪子的種類和顏色眾多紛雜,一旁尚未配對成雙的襪子數列就可能因此慢慢增長,致使我們每次從衣物堆裡拿出一隻襪子時,就得要過目一整排落單的襪子。當事物數量龐大時,瀏覽一整排線性事物,亦即陣列(array)非常耗時,因為你的目標物有可能位在那一陣列的末端,是以你非得要查閱完一整排陣列不可。
一九五三年,任職於IBM的數學家路恩(Hans Peter Luhn)想出了另外一種資料結構,有助於改善「陣列查找」所存有費時緩慢的潛在特性。這一資料結構稱之為相關陣列(associative array)、字典(dictionary)或雜湊表(hash table)……再說下去就是在可憐瑪姬的傷口上撒鹽了。雜湊表的運作方式基本上和陣列一模一樣,都是把資料儲存在一串集合裡,除了調換順序(亦即,一大批黑色的襪子之後緊接著少數幾隻紅色的襪子)以便立即查找之外,而這也稱作執行效率為常數時間(constant-time)的查找。
名為「常數時間」是因為查找不再受制於陣列的長度,換言之,查找速度與陣列長度無關。雖然此一結論並非屢次應驗,但總八九不離十,而這種始終會有例外的情況在電腦軟體裡經常發生,所以也讓許多研究人員和實務工作者頭痛不已,說穿了,電腦軟體並不像自然界存有基本法則。在我們的情境中,我們是假設數量不多且互不相同的襪子使得瑪姬的神經突觸(synapses)可以被快速激發,因而能產生立即的反應。
如同我們接下來會看到的,大部分執行效率為常數時間的查找都使用了一組方程式來建構工作任務,是以不須逐步完成任務,也不須反覆運算眼前的所有資料項目。以雜湊表來說,這一方程式就稱作雜湊函數(hash function),而雜湊函數的職責便是將某資料項目放入某一資料群,並能在往後快速檢索出這一資料項目。
然而,這些都只是額外補充的知識。我們從本章的故事場景學會的重點在於,善用已知訊息得出的方法會大大提升完成工作的速度。這一觀念在我們的任務是必須反覆執行相同動作時更能帶來莫大幫助。比方說,在商店裡的一盒字母蠟燭中,翻找要裝飾在女兒生日蛋糕上的特定字母;或是當你要洗衣服時,要將白色衣物和其他顏色或特殊材質的衣物區分開來;又或者是在益智競賽中,想盡辦法要在一套散亂的字母裡拼湊出一個字數最長的單字,如同英國電視節目《倒數計時》(Countdown)裡參賽者必須在三十秒內,從眼前的九個字母裡想出可組合成的最長單字那般。
在上述的各種情況裡,不妨先自問,眼前的任務是否可利用自己或是外在環境的記憶來加快速度。在面對成堆襪子的情境裡,只要持續保有一列尚未配對成功的襪子,你會發現其變化樣態不會超過五種。而就字母蠟燭的情境來說,當你在盒子裡看見所需字母的其中任四個字母時,就可以先將它們挑揀出來,而不是按照順序先找尋「L」,接著再找尋「U」……
在洗衣服的情境裡,你或許可以事先將髒衣服分別放在三個不同的洗衣籃裡,如此就省去了到時得在衣物堆裡翻找檢查的麻煩。至於組合出最長單字的情境,你可以先找出乍看之下能拼湊出的任一單字,再想想是否能藉由時態變化或複數型式等,將單字的長度拉長。在這種情況中,你一開始選擇的字母組合就是隨後所造出字詞的前綴(因此發揮了記憶的作用)。有一種稱之為字典樹(trie)的有趣樹狀結構就是以此種方式運作。字典樹可以探查出字詞或數字共有的前綴,再利用這項已知訊息讓拼字檢查,或你可能會在搜尋框裡輸入字詞的自動完成等變得更加快速。
以上內容由商周出版授權刊登,未經允許請勿轉載。
◎更多精彩內容,請見:《做決定不要靠運氣:從出門購物到分類郵件,用演算法找出人生最佳解》