LRU (Least Recently Used,最近最少使用) 是經典的緩存淘汰策略:當緩存滿時,移除最久未訪問的項目。核心邏輯:每次訪問(get/set)將鍵移至隊列頭部,淘汰時移除隊尾。
應用場景:CPU 緩存、虛擬內存頁面置換、Redis 緩存、瀏覽器緩存等。
OrderedDict 保持鍵的插入順序,move_to_end() 和 popitem(last=False) 完美契合 LRU 需求。
from collections import OrderedDict
class LRUCache(OrderedDict):
"""基於 OrderedDict 的 LRU 緩存
注意:不支持可變類型值、非線程安全
"""
def __init__(self, capacity: int):
super().__init__()
self.capacity = capacity
def get(self, key):
if key not in self:
return None
# 移至末尾(最近訪問)
self.move_to_end(key)
return self[key]
def put(self, key, value):
if key in self:
# 更新值並移至末尾
self.move_to_end(key)
elif len(self) >= self.capacity:
# 容量滿,移除最舊(隊首)
self.popitem(last=False)
self[key] = value
cache = LRUCache(3)
cache.put('a', 1)
cache.put('b', 2)
cache.put('c', 3)
print(list(cache.keys())) # ['a', 'b', 'c']
cache.get('a') # 訪問 a
print(list(cache.keys())) # ['b', 'c', 'a'] a 移至末尾
cache.put('d', 4) # 淘汰最舊 b
print(list(cache.keys())) # ['c', 'a', 'd']
用字典存儲鍵值,列表維護訪問順序。操作較繁瑣,性能較差(list.remove 為 O(n))。
class LRUCacheManual:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # key -> value
self.order = [] # key 列表,頭部最舊,尾部最新
def get(self, key):
if key not in self.cache:
return None
# 移至尾部
self.order.remove(key)
self.order.append(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.order.remove(key)
elif len(self.cache) >= self.capacity:
oldest = self.order.pop(0)
del self.cache[oldest]
self.cache[key] = value
self.order.append(key)
若存儲列表、字典等可變對象,get 返回的是同一引用,外部修改會影響緩存內部數據。
解決方案:
json.dumps/pickle),取出時反序列化。get 返回深拷貝(copy.deepcopy),性能較差。多線程環境下必須加鎖(threading.RLock),特別是 put 操作涉及多步字典/列表修改。
import threading
class ThreadSafeLRU(LRUCache):
def __init__(self, capacity):
super().__init__(capacity)
self._lock = threading.RLock()
def get(self, key):
with self._lock:
return super().get(key)
def put(self, key, value):
with self._lock:
super().put(key, value)
裝飾器形式,專為函數結果緩存設計:
from functools import lru_cache
@lru_cache(maxsize=128)
def expensive_computation(x, y):
# 複雜計算
return result
自動處理鍵構造(參數元組)、線程安全、統計信息(cache_info())。
| 方案 | 優點 | 缺點 | 適用場景 |
|---|---|---|---|
OrderedDict | 代碼簡潔、O(1)操作、標準庫無依賴 | 需自行處理可變值、線程安全 | 通用鍵值緩存、面試手寫實現 |
dict+list | 原理透明、無特殊依賴 | remove 為 O(n)、代碼冗長 | 教學演示、極簡環境 |
functools.lru_cache | 開箱即用、線程安全、統計功能 | 僅限函數緩存、鍵為參數元組 | 函數結果記憶化、遞歸優化 |