分類整理不是最好的歸檔方式?快取演算法告訴你最有效率的做法

2017.12.14 by
數位書選
shutterstock
資料龐雜、雜物繁多,如果要分類建檔,經常得花上一整天整理,不過,若從快取演算法來看,只需要把剛使用完的物品放在最上方,就是最有效率的做法。「需要的檔案應該盡量接近使用地點」的概念,你也認同嗎?

本文摘自:《決斷的演算》,行路出版

把隔最久才會再用的資料剔除──貝雷迪演算法

到了某個時候,只要多學一些知識,就會忘記一些你原本已經知道的事情快取裝滿時,如果還需要存放其他資料,就必須騰出空間,在電腦科學中,這個騰出空間的程序稱為快取替換(cache replacement)或快取剔除(cache eviction)。

這類演算法稱為替換策略(replacement policy)或剔除策略(eviction policy),或者直接稱為快取演算法。其中最重要的大概是外號「雷斯」的萊斯洛.貝雷迪(László Bélády)設計的演算法。這篇論文說明,快取管理的目標,是盡量減少在快取中找不到需要的資料,以致必須轉而至速度較慢的主記憶體尋找的狀況。這類狀況稱為尋頁錯失(page fault)或快取未中(cache miss)。貝雷迪在論文中提到,最佳的快取剔除策略,是快取裝滿時就剔除最久之後才會再次需要的資料。

當然,要預測何時會再次需要哪些資料說來容易,做起來可沒那麼簡單。

這個無所不知、有先見之明、能預測未來並執行已知最佳策略的演算法,稱為貝雷迪演算法(Bélády’s Algorithm) ,它是電腦科學家說的「預知型」演算法,也就是由預測的資料獲取資訊的演算法。聽起來很扯其實不然,只是預測未來通常沒那麼容易,軟體工程師也經常開玩笑說,在實際運用貝雷迪演算法時碰到「實作上的困難」。挑戰在於,我們要找到一種演算結果得盡可能接近預言的演算法,縱然大多時候我們只能被死死的卡在現在,而且僅能在有限程度上臆測即將發生的事。

我們可以直接採用隨機剔除(Random Eviction) ,把新資料放進快取,隨機覆寫舊資料。快取理論有個令人驚訝的初步結論就是,儘管這個方式不是十全十美,但還不算太差。事實上,只要有快取,不論我們怎麼運用,系統效率都能提高。我們常用的資料一定會很快又放回快取。另一個簡單的策略是先進先出( First In, First Out,FIFO) ,剔除或覆寫在快取裡停留最久的資料。第三種方式是最近最少使用法(Least Recently Used,LRU) :剔除未使用時間最長的資料。

史都華的建議不僅策略完全不同,而且其中之一顯然比較優異。貝雷迪以數種狀況比較過隨機剔除、先進先出和好幾種LRU,發現LRU的表現最接近預知。LRU原理的效果源自電腦科學家說的時序局部性(temporal locality):如果程式曾經呼叫某項資訊一次,不久後就可能再度呼叫。時序局部性有一部分源自電腦解決問題的方式(例如執行一個快速進行相關讀寫的迴圈),但其實人類解決問題的方式也有時序局部性。如果你用電腦工作,你可能會在電子郵件、瀏覽器和文書處理軟體之間不斷切換。如果你剛剛用過其中之一,代表可能會再用到它。如果沒有意外,上次使用時間離現在最久的程式,通常也會隔好一段時間才會用到。

街底的那片雲──距離非常重要

我們經常把網際網路視為扁平、獨立和關係鬆散的網絡,其實完全相反。我們也經常把網際網路視為抽象、虛擬和不受地理環境影響。資訊界說我們的資料放在「雲端」,也就是一個散漫又遙遠的地方。同樣地,這些說法也都不對。事實上,網際網路是一大把實體線路和一個個金屬機架,而且它受到的地理環境影響可能超乎你的想像。

工程師設計電腦硬體時,考慮的地理環境影響尺度非常小:速度較快的記憶體通常比較接近處理器,盡量縮短資料行經的線路。現在的處理器時脈循環都以十億赫茲計算,也就是每次運算的時間不到一奈秒。或者這麼說,光在這段時間裡只能行進幾公分,因此電腦內部的實體布局非常重要。如果把同樣的原理套用到非常大的尺度,對於線路長達幾千公里的網際網路而言,實際地理環境就顯得十分重要。

如果你存放網頁內容快取的硬體所在位置更接近使用者,就能更快提供這些網頁。目前網路的資料流量大多由內容分配網路(CDN)管理,這個網路在世界各地都有電腦,存放較受歡迎的某些網站的內容副本。如此一來,呼叫這些網頁的使用者就能直接取用鄰近電腦中的資料,不需要跨越重重大陸到原始伺服器去取用。

「需要的檔案應該盡量接近使用地點」的概念,同樣適用純實體環境。舉例來說,亞馬遜書店規模龐大的出貨中心,通常會避免採圖書館或百貨公司這類人類能理解的整理方式,而要員工把貨品隨意放在倉庫裡的任何地方(電池可能放在削鉛筆機、尿布、烤肉架和鐵吉他學習軟體旁邊),再用條碼把每樣貨品的位置標註在中央資料庫中。不過這類刻意表面凌亂的儲存系統仍然有個看得見的例外:需求較大的貨品會擺在不同區域,比其他貨品更容易取用。這塊區域就是亞馬遜的快取。

shutterstock

亞馬遜把這個原理向前推進一步,並以這項創新發明取得專利。這項專利的主旨稱為「預測包裹寄送」,根據媒體的說法,亞馬遜能在消費者下手購買之前就寄出貨品。亞馬遜跟其他科技公司一樣,希望擁有類似貝雷迪演算法的預測能力,但在規劃這項最新發展時,他們採用了快取概念。它這項專利其實是把最近在某個地區很受歡迎的貨品,運送到位於該地區的臨時倉庫,就像擁有實體貨品的CDN一樣。接著當消費者下單時,貨品距離消費者已經很近。預測個人的購買行為是不小的挑戰,但要預測幾千人的購買行為,大數法則就能派上用場了。好比說,某一天在柏克萊有人打算訂購回收紙漿衛生紙,當他們下單之後,衛生紙已經在運送途中了。

家中的快取──收納空間

雖然快取是為了整理電腦內部的數位資料而誕生,但顯然也很適合用來整理實際物品。

這些問題都很相似,因此我們說不定能把電腦科學提供的解決方案,運用到家裡。首先,當你決定要保留或捨棄哪些東西,LRU可能就是不錯的原則,至少比先進先出好上許多。如果你念大學時買的T恤有時還會穿,就不一定要丟掉。但已經好久沒穿的格紋長褲呢?送到二手商店去說不定還比較能遇上有緣人。

第二,充分運用地理環境。你通常在哪裡使用這個物品,就把那東西放在離那個地方最近的快取裡。教你收納的書大多沒有這樣的具體建議,但許多人認為有用的整理方案則經常提到這一點。舉例來說,有人說過茱莉.摩根斯坦(Julie Morgenstern)的《收納其實很容易》(Organizing from the Inside Out)有這麼一段話:「我把跑步和運動用品放在前門衣櫃底部的箱子裡。我希望它盡量接近大門。」

尚未成為櫥櫃整理原則的最後一個理論,是多層級記憶體階層。具備快取可提升效率,但具備容量最小且速度最快、到容量最大但速度最慢等多個層級的快取,可能更好。以你的收納空間而言,櫥櫃是一個快取層級、地下室是第二個,便利倉是第三個(當然,存取速度會隨層級而越來越慢,所以你應該依據LRU原理,來決定哪些物品要從每個層級剔除到下一個層級)。不過我們或許還能添加一層快取來加快速度,也就是再買一個比櫥櫃更小、取用速度更快也更接近的收納箱。

關於書面資料怎麼歸檔,收納專家大多說錯了

決定保留和捨棄哪些東西之後,最後一個挑戰就是該如何整理它們。我們已經討論過哪些東西要放進櫥櫃,以及櫥櫃應該放在哪裡,但該怎麼整理櫥櫃裡的東西呢?

目前我們經常看到的居家整理建議中,有個常見原則是「把類似的東西集中起來」,野口悠紀雄應該是目前唯一持相反看法的人,他說:「我必須強調一點,我的整理方法的基本原則,不是依據內容來分類檔案。」野口是東京大學經濟學家,寫過一系列為整理辦公室和人生提供「超級」技巧的書籍,包括《超級說服法》、《超級工作法》、《超級學習法》,以及跟本書最有關的《超級整理法》等。

shutterstock

野口剛開始研究經濟學時,經常被信件、資料和手稿等大量資料淹沒,每天花許多時間整理,因此開始尋找解決方案。一開始他只是把每份文件放進檔案夾,檔案夾上標註文件標題和日期,然後把檔案夾全部放進大箱子。由於不需要考慮每份文件的正確位置,這樣確實能節省時間,但這樣沒有任何次序可言。到了1990年代初,他締造了重大突破:他開始一律把檔案插入箱子的左手邊──他稱之為「超級整理法」。

野口指出,不論新檔案還是舊檔案,都適用左邊插入法:每次取出檔案用過後要放回箱子時,一定要放到最左邊。找檔案時也一定要從最左邊找起。如此一來,最先看到的就是最近使用過的檔案。

野口解釋,他會這麼做,一開始只是因為塞到最左邊比塞回原處容易得多。但他後來慢慢發現,這種方式不只比較簡單,而且有效率得多。

用過一件物品後要放回去時,野口歸檔系統當然可以節省時間,然而這種方式是否容易找到需要的檔案,仍然是個問題。畢竟其他效率大師都建議我們,把類似物品集中在一起,跟野口的方法完全不同。

不過電腦科學告訴了我們一件效率大師沒辦法保證的事。

雖然野口當時並不知道,但他的歸檔系統其實就是LRU原理(最近最少使用法)的延伸。LRU告訴我們,把新內容加入快取時應該剔除最舊的內容,但沒有告訴我們應該把新內容放在哪裡。1970和1980年代電腦科學家進行的一連串研究,解答了這個問題。當時他們遇到的問題稱為自組織列表問題,狀況跟野口的歸檔困境幾乎完全相同。假如你有一組依順序排列的物品,你必須定時搜尋,找出其中某些物品。搜尋行為本身必須是線性,因為你必須從頭開始逐一看過每件物品,但你找到需要的物品之後,可以放回任何位置。此時你應該把物品放在哪裡,才能盡可能提高搜尋效率?

shutterstock

丹尼爾.史利特(Daniel Sleator)和羅伯.塔爾占(Robert Tarjan)於1985年發表關於自組織列表的重要論文,以古典電腦科學方式探討在所有可能要求順序下,以各種方式列表的最差情況表現。依照直覺,搜尋從前端開始,所以我們排列順序時,也希望把最可能用到的物品放在最前端。但最可能用到的物品又是什麼?這又回到預測未來能力的問題了。史利特和塔爾占的研究結果顯示,某些「十分簡單的自調整方案,居然具備一定程度的」預知能力。也就是說,如果我們遵照LRU原理,每次都把物品放回列表的最前端,那麼搜尋所花的時間,絕對不會超過我們能預知未來時的兩倍。其他演算法都沒辦法保證這一點。

了解野口歸檔系統是LRU原理的實行範例可讓我們了解,LRU原理不只更有效率,而且是最佳方法。

史利特和塔爾占的研究結果,還提出另一種變化──把野口歸檔系統旋轉90度就是了。簡單地說,一箱檔案夾轉個90度就變成一疊檔案,如此一來搜尋檔案時自然會從上到下,每次抽出文件後要放回去時不會放回原處,而會放在最上面。

簡而言之,自組織列表的數學原理提出了一個十分創新的概念:在書桌上堆一大疊文件不但不是雜亂象徵,還是目前已知最精良、效率最佳的資料結構,沒必要因而有罪惡感。在別人看來那或許是凌亂、欠缺條理,其實它自有一套條理。由於我們無法預知未來,所以把用過的東西放回最上方是最好的辦法。

延伸閱讀

每日精選科技圈重要消息