4.4 記憶體與快取 *¶
在本章的前兩節中，我們探討了陣列和鏈結串列這兩種基礎且重要的資料結構，它們分別代表了“連續儲存”和“分散儲存”兩種物理結構。
實際上，物理結構在很大程度上決定了程式對記憶體和快取的使用效率，進而影響演算法程式的整體效能。
4.4.1 計算機儲存裝置¶
計算機中包括三種類型的儲存裝置：硬碟（hard disk）、記憶體（random-access memory, RAM）、快取（cache memory）。表 4-2 展示了它們在計算機系統中的不同角色和效能特點。
表 4-2 計算機的儲存裝置
| 硬碟 | 記憶體 | 快取 | |
|---|---|---|---|
| 用途 | 長期儲存資料，包括作業系統、程式、檔案等 | 臨時儲存當前執行的程式和正在處理的資料 | 儲存經常訪問的資料和指令，減少 CPU 訪問記憶體的次數 |
| 易失性 | 斷電後資料不會丟失 | 斷電後資料會丟失 | 斷電後資料會丟失 |
| 容量 | 較大，TB 級別 | 較小，GB 級別 | 非常小，MB 級別 |
| 速度 | 較慢，幾百到幾千 MB/s | 較快，幾十 GB/s | 非常快，幾十到幾百 GB/s |
| 價格 | 較便宜，幾毛到幾元 / GB | 較貴，幾十到幾百元 / GB | 非常貴，隨 CPU 打包計價 |
我們可以將計算機儲存系統想象為圖 4-9 所示的金字塔結構。越靠近金字塔頂端的儲存裝置的速度越快、容量越小、成本越高。這種多層級的設計並非偶然，而是計算機科學家和工程師們經過深思熟慮的結果。
- 硬碟難以被記憶體取代。首先，記憶體中的資料在斷電後會丟失，因此它不適合長期儲存資料；其次，記憶體的成本是硬碟的幾十倍，這使得它難以在消費者市場普及。
- 快取的大容量和高速度難以兼得。隨著 L1、L2、L3 快取的容量逐步增大，其物理尺寸會變大，與 CPU 核心之間的物理距離會變遠，從而導致資料傳輸時間增加，元素訪問延遲變高。在當前技術下，多層級的快取結構是容量、速度和成本之間的最佳平衡點。
圖 4-9 計算機儲存系統
Tip
計算機的儲存層次結構體現了速度、容量和成本三者之間的精妙平衡。實際上，這種權衡普遍存在於所有工業領域，它要求我們在不同的優勢和限制之間找到最佳平衡點。
總的來說，硬碟用於長期儲存大量資料，記憶體用於臨時儲存程式執行中正在處理的資料，而快取則用於儲存經常訪問的資料和指令，以提高程式執行效率。三者共同協作，確保計算機系統高效執行。
如圖 4-10 所示，在程式執行時，資料會從硬碟中被讀取到記憶體中，供 CPU 計算使用。快取可以看作 CPU 的一部分，它透過智慧地從記憶體載入資料，給 CPU 提供高速的資料讀取，從而顯著提升程式的執行效率，減少對較慢的記憶體的依賴。
圖 4-10 硬碟、記憶體和快取之間的資料流通
4.4.2 資料結構的記憶體效率¶
在記憶體空間利用方面，陣列和鏈結串列各自具有優勢和侷限性。
一方面，記憶體是有限的，且同一塊記憶體不能被多個程式共享，因此我們希望資料結構能夠儘可能高效地利用空間。陣列的元素緊密排列，不需要額外的空間來儲存鏈結串列節點間的引用（指標），因此空間效率更高。然而，陣列需要一次性分配足夠的連續記憶體空間，這可能導致記憶體浪費，陣列擴容也需要額外的時間和空間成本。相比之下，鏈結串列以“節點”為單位進行動態記憶體分配和回收，提供了更大的靈活性。
另一方面，在程式執行時，隨著反覆申請與釋放記憶體，空閒記憶體的碎片化程度會越來越高，從而導致記憶體的利用效率降低。陣列由於其連續的儲存方式，相對不容易導致記憶體碎片化。相反，鏈結串列的元素是分散儲存的，在頻繁的插入與刪除操作中，更容易導致記憶體碎片化。
4.4.3 資料結構的快取效率¶
快取雖然在空間容量上遠小於記憶體，但它比記憶體快得多，在程式執行速度上起著至關重要的作用。由於快取的容量有限，只能儲存一小部分頻繁訪問的資料，因此當 CPU 嘗試訪問的資料不在快取中時，就會發生快取未命中（cache miss），此時 CPU 不得不從速度較慢的記憶體中載入所需資料。
顯然，“快取未命中”越少，CPU 讀寫資料的效率就越高，程式效能也就越好。我們將 CPU 從快取中成功獲取資料的比例稱為快取命中率（cache hit rate），這個指標通常用來衡量快取效率。
為了儘可能達到更高的效率，快取會採取以下資料載入機制。
- 快取行：快取不是單個位元組地儲存與載入資料，而是以快取行為單位。相比於單個位元組的傳輸，快取行的傳輸形式更加高效。
- 預取機制：處理器會嘗試預測資料訪問模式（例如順序訪問、固定步長跳躍訪問等），並根據特定模式將資料載入至快取之中，從而提升命中率。
- 空間區域性：如果一個數據被訪問，那麼它附近的資料可能近期也會被訪問。因此，快取在載入某一資料時，也會載入其附近的資料，以提高命中率。
- 時間區域性：如果一個數據被訪問，那麼它在不久的將來很可能再次被訪問。快取利用這一原理，透過保留最近訪問過的資料來提高命中率。
實際上，陣列和鏈結串列對快取的利用效率是不同的，主要體現在以下幾個方面。
- 佔用空間：鏈結串列元素比陣列元素佔用空間更多，導致快取中容納的有效資料量更少。
- 快取行：鏈結串列資料分散在記憶體各處，而快取是“按行載入”的，因此載入到無效資料的比例更高。
- 預取機制：陣列比鏈結串列的資料訪問模式更具“可預測性”，即系統更容易猜出即將被載入的資料。
- 空間區域性：陣列被儲存在集中的記憶體空間中，因此被載入資料附近的資料更有可能即將被訪問。
總體而言，陣列具有更高的快取命中率，因此它在操作效率上通常優於鏈結串列。這使得在解決演算法問題時，基於陣列實現的資料結構往往更受歡迎。
需要注意的是，高快取效率並不意味著陣列在所有情況下都優於鏈結串列。實際應用中選擇哪種資料結構，應根據具體需求來決定。例如，陣列和鏈結串列都可以實現“堆疊”資料結構（下一章會詳細介紹），但它們適用於不同場景。
- 在做演算法題時，我們會傾向於選擇基於陣列實現的堆疊，因為它提供了更高的操作效率和隨機訪問的能力，代價僅是需要預先為陣列分配一定的記憶體空間。
- 如果資料量非常大、動態性很高、堆疊的預期大小難以估計，那麼基於鏈結串列實現的堆疊更加合適。鏈結串列能夠將大量資料分散儲存於記憶體的不同部分，並且避免了陣列擴容產生的額外開銷。