引言

LRU 緩存是一種緩存替換策略，當(dāng)緩存空間不足時(shí)，會(huì)移除最久未使用的數(shù)據(jù)以騰出空間存放新的數(shù)據(jù)。LRU 緩存的特點(diǎn)：

1. 有限容量：緩存擁有固定的容量，當(dāng)容量滿時(shí)，需要移除舊數(shù)據(jù)。
2. 淘汰策略：將最久未使用的緩存項(xiàng)移除。
3. 快速訪問(wèn)：訪問(wèn)，插入，刪除的復(fù)雜度位 O(1)。

本文將介紹 OrderedDict 實(shí)現(xiàn) Least Recently used（LRU）緩存的方法。

正文

from collections import OrderedDictclass LRUCache:def __init__(self, capacity: int):self.cache = OrderedDict()self.capacity = capacitydef get(self, key: str) -> int:if key not in self.cache:return -1self.cache.move_to_end(key)return self.cache[key]def put(self, key: str, value: int) -> None:if key in self.cache:self.cache.move_to_end(key)self.cache[key] = valueif len(self.cache) > self.capacity:self.cache.popitem(last=False)if __name__ == '__main__':lru = LRUCache(2)lru.put('a', 1)lru.put('b', 2)print(lru.get('a'))  # 1lru.put('c', 3)print(lru.get('b'))  # -1

當(dāng)使用 print(lru.get('a')) 語(yǔ)句輸出結(jié)果時(shí)，鍵值對(duì) 'a':1 會(huì)被放在 OrderedDict 最后的位置，lru.put('c', 3) 會(huì)導(dǎo)致位于開始位置的元素 'b':2 被刪除。當(dāng)我們?cè)俅问褂?print(lru.get('b')) 訪問(wèn) 'b':2 元素時(shí)會(huì)得到返回值 -1 提示我們當(dāng)前緩存中已經(jīng)不存在該元素。

如果大家覺得有用，就點(diǎn)個(gè)贊讓更多的人看到吧~