Python OrderedDict 实现 Least Recently used（LRU）缓存

引言

LRU 缓存是一种缓存替换策略，当缓存空间不足时，会移除最久未使用的数据以腾出空间存放新的数据。LRU 缓存的特点：

1. 有限容量：缓存拥有固定的容量，当容量满时，需要移除旧数据。
2. 淘汰策略：将最久未使用的缓存项移除。
3. 快速访问：访问，插入，删除的复杂度位 O(1)。

本文将介绍 OrderedDict 实现 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

当使用 print(lru.get('a')) 语句输出结果时，键值对 'a':1 会被放在 OrderedDict 最后的位置，lru.put('c', 3) 会导致位于开始位置的元素 'b':2 被删除。当我们再次使用 print(lru.get('b')) 访问 'b':2 元素时会得到返回值 -1 提示我们当前缓存中已经不存在该元素。

如果大家觉得有用，就点个赞让更多的人看到吧~