本文摘自：《決斷的演算》，行路出版
把隔最久才會再用的資料剔除──貝雷迪演算法
到了某個時候，只要多學一些知識，就會忘記一些你原本已經知道的事情快取裝滿時，如果還需要存放其他資料，就必須騰出空間，在電腦科學中，這個騰出空間的程序稱為快取替換（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）管理，這個網路在世界各地都有電腦，存放較受歡迎的某些網站的內容副本。如此一來，呼叫這些網頁的使用者就能直接取用鄰近電腦中的資料，不需要跨越重重大陸到原始伺服器去取用。
「需要的檔案應該盡量接近使用地點」的概念，同樣適用純實體環境。舉例來說，亞馬遜書店規模龐大的出貨中心，通常會避免採圖書館或百貨公司這類人類能理解的整理方式，而要員工把貨品隨意放在倉庫裡的任何地方（電池可能放在削鉛筆機、尿布、烤肉架和鐵吉他學習軟體旁邊），再用條碼把每樣貨品的位置標註在中央資料庫中。不過這類刻意表面凌亂的儲存系統仍然有個看得見的例外：需求較大的貨品會擺在不同區域，比其他貨品更容易取用。這塊區域就是亞馬遜的快取。
亞馬遜把這個原理向前推進一步，並以這項創新發明取得專利。這項專利的主旨稱為「預測包裹寄送」，根據媒體的說法，亞馬遜能在消費者下手購買之前就寄出貨品。亞馬遜跟其他科技公司一樣，希望擁有類似貝雷迪演算法的預測能力，但在規劃這項最新發展時，他們採用了快取概念。它這項專利其實是把最近在某個地區很受歡迎的貨品，運送到位於該地區的臨時倉庫，就像擁有實體貨品的CDN一樣。接著當消費者下單時，貨品距離消費者已經很近。預測個人的購買行為是不小的挑戰，但要預測幾千人的購買行為，大數法則就能派上用場了。好比說，某一天在柏克萊有人打算訂購回收紙漿衛生紙，當他們下單之後，衛生紙已經在運送途中了。
家中的快取──收納空間
雖然快取是為了整理電腦內部的數位資料而誕生，但顯然也很適合用來整理實際物品。
這些問題都很相似，因此我們說不定能把電腦科學提供的解決方案，運用到家裡。首先，當你決定要保留或捨棄哪些東西，LRU可能就是不錯的原則，至少比先進先出好上許多。如果你念大學時買的T恤有時還會穿，就不一定要丟掉。但已經好久沒穿的格紋長褲呢？送到二手商店去說不定還比較能遇上有緣人。
第二，充分運用地理環境。你通常在哪裡使用這個物品，就把那東西放在離那個地方最近的快取裡。教你收納的書大多沒有這樣的具體建議，但許多人認為有用的整理方案則經常提到這一點。舉例來說，有人說過茱莉．摩根斯坦（Julie Morgenstern）的《收納其實很容易》（Organizing from the Inside Out）有這麼一段話：「我把跑步和運動用品放在前門衣櫃底部的箱子裡。我希望它盡量接近大門。」
尚未成為櫥櫃整理原則的最後一個理論，是多層級記憶體階層。具備快取可提升效率，但具備容量最小且速度最快、到容量最大但速度最慢等多個層級的快取，可能更好。以你的收納空間而言，櫥櫃是一個快取層級、地下室是第二個，便利倉是第三個（當然，存取速度會隨層級而越來越慢，所以你應該依據LRU原理，來決定哪些物品要從每個層級剔除到下一個層級）。不過我們或許還能添加一層快取來加快速度，也就是再買一個比櫥櫃更小、取用速度更快也更接近的收納箱。
關於書面資料怎麼歸檔，收納專家大多說錯了
決定保留和捨棄哪些東西之後，最後一個挑戰就是該如何整理它們。我們已經討論過哪些東西要放進櫥櫃，以及櫥櫃應該放在哪裡，但該怎麼整理櫥櫃裡的東西呢？
目前我們經常看到的居家整理建議中，有個常見原則是「把類似的東西集中起來」，野口悠紀雄應該是目前唯一持相反看法的人，他說：「我必須強調一點，我的整理方法的基本原則，不是依據內容來分類檔案。」野口是東京大學經濟學家，寫過一系列為整理辦公室和人生提供「超級」技巧的書籍，包括《超級說服法》、《超級工作法》、《超級學習法》，以及跟本書最有關的《超級整理法》等。
野口剛開始研究經濟學時，經常被信件、資料和手稿等大量資料淹沒，每天花許多時間整理，因此開始尋找解決方案。一開始他只是把每份文件放進檔案夾，檔案夾上標註文件標題和日期，然後把檔案夾全部放進大箱子。由於不需要考慮每份文件的正確位置，這樣確實能節省時間，但這樣沒有任何次序可言。到了1990年代初，他締造了重大突破：他開始一律把檔案插入箱子的左手邊──他稱之為「超級整理法」。
野口指出，不論新檔案還是舊檔案，都適用左邊插入法：每次取出檔案用過後要放回箱子時，一定要放到最左邊。找檔案時也一定要從最左邊找起。如此一來，最先看到的就是最近使用過的檔案。
野口解釋，他會這麼做，一開始只是因為塞到最左邊比塞回原處容易得多。但他後來慢慢發現，這種方式不只比較簡單，而且有效率得多。
用過一件物品後要放回去時，野口歸檔系統當然可以節省時間，然而這種方式是否容易找到需要的檔案，仍然是個問題。畢竟其他效率大師都建議我們，把類似物品集中在一起，跟野口的方法完全不同。
不過電腦科學告訴了我們一件效率大師沒辦法保證的事。
雖然野口當時並不知道，但他的歸檔系統其實就是LRU原理（最近最少使用法）的延伸。LRU告訴我們，把新內容加入快取時應該剔除最舊的內容，但沒有告訴我們應該把新內容放在哪裡。1970和1980年代電腦科學家進行的一連串研究，解答了這個問題。當時他們遇到的問題稱為自組織列表問題，狀況跟野口的歸檔困境幾乎完全相同。假如你有一組依順序排列的物品，你必須定時搜尋，找出其中某些物品。搜尋行為本身必須是線性，因為你必須從頭開始逐一看過每件物品，但你找到需要的物品之後，可以放回任何位置。此時你應該把物品放在哪裡，才能盡可能提高搜尋效率？
丹尼爾．史利特（Daniel Sleator）和羅伯．塔爾占（Robert Tarjan）於1985年發表關於自組織列表的重要論文，以古典電腦科學方式探討在所有可能要求順序下，以各種方式列表的最差情況表現。依照直覺，搜尋從前端開始，所以我們排列順序時，也希望把最可能用到的物品放在最前端。但最可能用到的物品又是什麼？這又回到預測未來能力的問題了。史利特和塔爾占的研究結果顯示，某些「十分簡單的自調整方案，居然具備一定程度的」預知能力。也就是說，如果我們遵照LRU原理，每次都把物品放回列表的最前端，那麼搜尋所花的時間，絕對不會超過我們能預知未來時的兩倍。其他演算法都沒辦法保證這一點。
了解野口歸檔系統是LRU原理的實行範例可讓我們了解，LRU原理不只更有效率，而且是最佳方法。
史利特和塔爾占的研究結果，還提出另一種變化──把野口歸檔系統旋轉90度就是了。簡單地說，一箱檔案夾轉個90度就變成一疊檔案，如此一來搜尋檔案時自然會從上到下，每次抽出文件後要放回去時不會放回原處，而會放在最上面。
簡而言之，自組織列表的數學原理提出了一個十分創新的概念：在書桌上堆一大疊文件不但不是雜亂象徵，還是目前已知最精良、效率最佳的資料結構，沒必要因而有罪惡感。在別人看來那或許是凌亂、欠缺條理，其實它自有一套條理。由於我們無法預知未來，所以把用過的東西放回最上方是最好的辦法。
