萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 實現 LRU 緩存算法的兩種方法:OrderedDict 與 dict+list 對比

LRU 算法簡介

LRU (Least Recently Used,最近最少使用) 是經典的緩存淘汰策略:當緩存滿時,移除最久未訪問的項目。核心邏輯:每次訪問(get/set)將鍵移至隊列頭部,淘汰時移除隊尾。

應用場景:CPU 緩存、虛擬內存頁面置換、Redis 緩存、瀏覽器緩存等。

方法一:使用 collections.OrderedDict(推薦)

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']

方法二:手動實現 dict + list(教學用)

用字典存儲鍵值,列表維護訪問順序。操作較繁瑣,性能較差(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)

關鍵問題與解決方案

1. 可變類型值的共享引用問題

若存儲列表、字典等可變對象,get 返回的是同一引用,外部修改會影響緩存內部數據。

解決方案:

  • 序列化存儲(如 json.dumps/pickle),取出時反序列化。
  • get 返回深拷貝(copy.deepcopy),性能較差。

2. 線程安全

多線程環境下必須加鎖(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)

Python 3.2+ 內置方案:functools.lru_cache

裝飾器形式,專為函數結果緩存設計:

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開箱即用、線程安全、統計功能僅限函數緩存、鍵為參數元組函數結果記憶化、遞歸優化
copyright © 萬盛學電腦網 all rights reserved