---
comments: true
status: new
---

# 4.4 &nbsp; 記憶體與快取 *

在本章的前兩節中，我們探討了陣列和鏈結串列這兩種基礎且重要的資料結構，它們分別代表了“連續儲存”和“分散儲存”兩種物理結構。

實際上，**物理結構在很大程度上決定了程式對記憶體和快取的使用效率**，進而影響演算法程式的整體效能。

## 4.4.1 &nbsp; 計算機儲存裝置

計算機中包括三種類型的儲存裝置：<u>硬碟（hard disk）</u>、<u>記憶體（random-access memory, RAM）</u>、<u>快取（cache memory）</u>。表 4-2 展示了它們在計算機系統中的不同角色和效能特點。

<p align="center"> 表 4-2 &nbsp; 計算機的儲存裝置 </p>

<div class="center-table" markdown>

|        | 硬碟                                     | 記憶體                                   | 快取                                              |
| ------ | ---------------------------------------- | -------------------------------------- | ------------------------------------------------- |
| 用途   | 長期儲存資料，包括作業系統、程式、檔案等 | 臨時儲存當前執行的程式和正在處理的資料 | 儲存經常訪問的資料和指令，減少 CPU 訪問記憶體的次數 |
| 易失性 | 斷電後資料不會丟失                       | 斷電後資料會丟失                       | 斷電後資料會丟失                                  |
| 容量   | 較大，TB 級別                            | 較小，GB 級別                          | 非常小，MB 級別                                   |
| 速度   | 較慢，幾百到幾千 MB/s                    | 較快，幾十 GB/s                        | 非常快，幾十到幾百 GB/s                           |
| 價格   | 較便宜，幾毛到幾元 / GB                  | 較貴，幾十到幾百元 / GB                | 非常貴，隨 CPU 打包計價                           |

</div>

我們可以將計算機儲存系統想象為圖 4-9 所示的金字塔結構。越靠近金字塔頂端的儲存裝置的速度越快、容量越小、成本越高。這種多層級的設計並非偶然，而是計算機科學家和工程師們經過深思熟慮的結果。

- **硬碟難以被記憶體取代**。首先，記憶體中的資料在斷電後會丟失，因此它不適合長期儲存資料；其次，記憶體的成本是硬碟的幾十倍，這使得它難以在消費者市場普及。
- **快取的大容量和高速度難以兼得**。隨著 L1、L2、L3 快取的容量逐步增大，其物理尺寸會變大，與 CPU 核心之間的物理距離會變遠，從而導致資料傳輸時間增加，元素訪問延遲變高。在當前技術下，多層級的快取結構是容量、速度和成本之間的最佳平衡點。

![計算機儲存系統](ram_and_cache.assets/storage_pyramid.png){ class="animation-figure" }

<p align="center"> 圖 4-9 &nbsp; 計算機儲存系統 </p>

!!! tip

    計算機的儲存層次結構體現了速度、容量和成本三者之間的精妙平衡。實際上，這種權衡普遍存在於所有工業領域，它要求我們在不同的優勢和限制之間找到最佳平衡點。

總的來說，**硬碟用於長期儲存大量資料，記憶體用於臨時儲存程式執行中正在處理的資料，而快取則用於儲存經常訪問的資料和指令**，以提高程式執行效率。三者共同協作，確保計算機系統高效執行。

如圖 4-10 所示，在程式執行時，資料會從硬碟中被讀取到記憶體中，供 CPU 計算使用。快取可以看作 CPU 的一部分，**它透過智慧地從記憶體載入資料**，給 CPU 提供高速的資料讀取，從而顯著提升程式的執行效率，減少對較慢的記憶體的依賴。

![硬碟、記憶體和快取之間的資料流通](ram_and_cache.assets/computer_storage_devices.png){ class="animation-figure" }

<p align="center"> 圖 4-10 &nbsp; 硬碟、記憶體和快取之間的資料流通 </p>

## 4.4.2 &nbsp; 資料結構的記憶體效率

在記憶體空間利用方面，陣列和鏈結串列各自具有優勢和侷限性。

一方面，**記憶體是有限的，且同一塊記憶體不能被多個程式共享**，因此我們希望資料結構能夠儘可能高效地利用空間。陣列的元素緊密排列，不需要額外的空間來儲存鏈結串列節點間的引用（指標），因此空間效率更高。然而，陣列需要一次性分配足夠的連續記憶體空間，這可能導致記憶體浪費，陣列擴容也需要額外的時間和空間成本。相比之下，鏈結串列以“節點”為單位進行動態記憶體分配和回收，提供了更大的靈活性。

另一方面，在程式執行時，**隨著反覆申請與釋放記憶體，空閒記憶體的碎片化程度會越來越高**，從而導致記憶體的利用效率降低。陣列由於其連續的儲存方式，相對不容易導致記憶體碎片化。相反，鏈結串列的元素是分散儲存的，在頻繁的插入與刪除操作中，更容易導致記憶體碎片化。

## 4.4.3 &nbsp; 資料結構的快取效率

快取雖然在空間容量上遠小於記憶體，但它比記憶體快得多，在程式執行速度上起著至關重要的作用。由於快取的容量有限，只能儲存一小部分頻繁訪問的資料，因此當 CPU 嘗試訪問的資料不在快取中時，就會發生<u>快取未命中（cache miss）</u>，此時 CPU 不得不從速度較慢的記憶體中載入所需資料。

顯然，**“快取未命中”越少，CPU 讀寫資料的效率就越高**，程式效能也就越好。我們將 CPU 從快取中成功獲取資料的比例稱為<u>快取命中率（cache hit rate）</u>，這個指標通常用來衡量快取效率。

為了儘可能達到更高的效率，快取會採取以下資料載入機制。

- **快取行**：快取不是單個位元組地儲存與載入資料，而是以快取行為單位。相比於單個位元組的傳輸，快取行的傳輸形式更加高效。
- **預取機制**：處理器會嘗試預測資料訪問模式（例如順序訪問、固定步長跳躍訪問等），並根據特定模式將資料載入至快取之中，從而提升命中率。
- **空間區域性**：如果一個數據被訪問，那麼它附近的資料可能近期也會被訪問。因此，快取在載入某一資料時，也會載入其附近的資料，以提高命中率。
- **時間區域性**：如果一個數據被訪問，那麼它在不久的將來很可能再次被訪問。快取利用這一原理，透過保留最近訪問過的資料來提高命中率。

實際上，**陣列和鏈結串列對快取的利用效率是不同的**，主要體現在以下幾個方面。

- **佔用空間**：鏈結串列元素比陣列元素佔用空間更多，導致快取中容納的有效資料量更少。
- **快取行**：鏈結串列資料分散在記憶體各處，而快取是“按行載入”的，因此載入到無效資料的比例更高。
- **預取機制**：陣列比鏈結串列的資料訪問模式更具“可預測性”，即系統更容易猜出即將被載入的資料。
- **空間區域性**：陣列被儲存在集中的記憶體空間中，因此被載入資料附近的資料更有可能即將被訪問。

總體而言，**陣列具有更高的快取命中率，因此它在操作效率上通常優於鏈結串列**。這使得在解決演算法問題時，基於陣列實現的資料結構往往更受歡迎。

需要注意的是，**高快取效率並不意味著陣列在所有情況下都優於鏈結串列**。實際應用中選擇哪種資料結構，應根據具體需求來決定。例如，陣列和鏈結串列都可以實現“堆疊”資料結構（下一章會詳細介紹），但它們適用於不同場景。

- 在做演算法題時，我們會傾向於選擇基於陣列實現的堆疊，因為它提供了更高的操作效率和隨機訪問的能力，代價僅是需要預先為陣列分配一定的記憶體空間。
- 如果資料量非常大、動態性很高、堆疊的預期大小難以估計，那麼基於鏈結串列實現的堆疊更加合適。鏈結串列能夠將大量資料分散儲存於記憶體的不同部分，並且避免了陣列擴容產生的額外開銷。
