LRU 快取教學：原理、程式碼與時間複雜度

LRU 快取解決什麼問題

快取會保存緩慢操作的結果，例如資料庫查詢、網路請求或昂貴的運算，讓重複的請求能快速得到回應。記憶體有限，所以快取在滿了之後必須決定要丟掉什麼。LRU 賭的是：最近用過的資料很快會再被用到，而很久沒碰的資料大概不會。這個賭注對許多真實的工作負載都很有效，這也是為什麼 CPU 快取、作業系統的分頁快取、資料庫、網頁伺服器與 CDN 中都能看到 LRU 及其近似做法。

概念：兩個結構合作

我們需要兩件事都很快：找到某個鍵，以及知道哪個鍵是最近最少使用的。只有雜湊表沒有順序，只有串列則搜尋太慢。兩者結合就能兩件事都做到：

執行 get(key) 時，先在雜湊表中找到節點，把它移到最前面，再回傳它的值。執行 put(key, value) 時，更新或建立最前面的節點；如果此時快取超過容量，就移除最後面的節點，並從雜湊表中刪除它的鍵。

容量為 2 的實例演練

從頭開始的 Python 實作

哨兵頭節點與尾節點讓空串列不再有特殊情況：每個真正的節點前後永遠都有節點。

class Node:
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()   # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        if key in self.map:
            self._unlink(self.map[key])
        node = self.map[key] = Node(key, value)
        self._push_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]

cache = LRUCache(2)
cache.put(1, "a")
cache.put(2, "b")
print(cache.get(1))   # a
cache.put(3, "c")     # evicts key 2
print(cache.get(2))   # None
cache.put(1, "A")
cache.put(4, "d")     # evicts key 3
print(cache.get(3), cache.get(1), cache.get(4))  # None A d

使用 OrderedDict 的簡短版本

collections.OrderedDict 本身就是雜湊表加雙向鏈結串列，而 move_to_end 與 popitem(last=False) 都是 O(1)。因此當你需要一個 LRU 快取物件時，這是 Python 中慣用的選擇。

from collections import OrderedDict

class LRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # mark as most recent
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # drop least recent

c = LRU(2)
c.put("x", 1)
c.put("y", 2)
c.get("x")
c.put("z", 3)
print(list(c.data))  # ['x', 'z']

用 functools.lru_cache 快取函式結果

要快取函式的回傳值，請使用 functools.lru_cache 裝飾器。引數必須是可雜湊的，因為它們會變成字典的鍵。cache_info() 會顯示命中次數、未命中次數與目前的大小。

from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(80))           # 23416728348467685
print(fib.cache_info())
# CacheInfo(hits=78, misses=81, maxsize=128, currsize=81)

maxsize=None 代表沒有上限的快取，這正是 functools.cache（Python 3.9 及之後）所做的事。呼叫 fib.cache_clear() 可清空快取。

時間與空間複雜度

變體、常見錯誤與何時使用 LRU

• LFU（least frequently used，最不常使用）會淘汰存取次數最少的項目；它能保護熱門項目不受一次性掃描的影響，但實作較複雜。
• 近似 LRU：像 Redis 這類系統會抽樣幾個鍵，並淘汰其中最舊的，而不是維護精確的串列，這樣可以節省記憶體。
• TTL 快取會在固定時間後讓項目過期，通常會搭配大小限制一起使用。
• 忘了在 get 時，或對既有的鍵執行 put 時，把項目移到最前面，會讓 LRU 變成 FIFO。
• 忘了從雜湊表中刪除被淘汰的鍵，會留下懸空的項目並造成記憶體洩漏。
• 在多個執行緒之間共用 LRU 快取時，每個操作都需要加鎖；functools.lru_cache 則可以安全地從多個執行緒呼叫。

當近期的使用能預測未來的使用時，LRU 是很好的預設選擇。當大量一次性掃描把常用資料擠出去時，它的表現就不好；這類工作負載更適合 LFU 或抗掃描的策略。設計出每個操作都是 O(1) 的 LRU 快取，也是最常見的程式面試題之一，因為它同時考驗雜湊表與鏈結串列。