Python口试题：在 Python 中，怎样实现一个 LRU（迩来最少使用）缓存？

在 Python 中，可以使用 collections.OrderedDict 或 functools.lru_cache 来实现一个 LRU（迩来最少使用）缓存。functools.lru_cache 是一个内置装饰器，可以直接用于缓存函数的效果。而假如你想实现一个自界说的 LRU 缓存，可以使用 collections.OrderedDict。
下面是使用 collections.OrderedDict 实现一个简单的 LRU 缓存的示例：

1. from collections import OrderedDict
3. class LRUCache:
4.     def __init__(self, capacity: int):
5.         self.cache = OrderedDict()
6.         self.capacity = capacity
8.     def get(self, key: int) -> int:
9.         if key not in self.cache:
10.             return -1
11.         else:
12.             self.cache.move_to_end(key)  # 将访问的key移动到末尾
13.             return self.cache[key]
15.     def put(self, key: int, value: int) -> None:
16.         if key in self.cache:
17.             self.cache.move_to_end(key)
18.         self.cache[key] = value
19.         if len(self.cache) > self.capacity:
20.             self.cache.popitem(last=False)  # 弹出最左侧（最旧）的元素
22. # 使用示例
23. lru_cache = LRUCache(2)
24. lru_cache.put(1, 1)
25. lru_cache.put(2, 2)
26. print(lru_cache.get(1))  # 返回 1
27. lru_cache.put(3, 3)      # 移除键 2
28. print(lru_cache.get(2))  # 返回 -1 (未找到)
29. lru_cache.put(4, 4)      # 移除键 1
30. print(lru_cache.get(1))  # 返回 -1 (未找到)
31. print(lru_cache.get(3))  # 返回 3
32. print(lru_cache.get(4))  # 返回 4

复制代码

在这个实现中，LRUCache 类使用 OrderedDict 来保持插入元素的序次。put 方法在插入新元素时，假如高出容量限定，则移除最旧的元素。get 方法在访问元素时，将其移动到末了，以体现迩来访问。
别的，假如你盼望更方便地使用 LRU 缓存，可以直接使用 functools.lru_cache 装饰器。以下是一个示例：

1. from functools import lru_cache
3. @lru_cache(maxsize=2)
4. def some_expensive_function(n):
5.     print(f"Computing {n}")
6.     return n * n
8. # 使用示例
9. print(some_expensive_function(2))  # 输出 "Computing 2" 和 4
10. print(some_expensive_function(3))  # 输出 "Computing 3" 和 9
11. print(some_expensive_function(2))  # 直接输出 4，不会打印 "Computing 2"
12. print(some_expensive_function(4))  # 输出 "Computing 4" 和 16
13. print(some_expensive_function(3))  # 再次计算 3，因为之前的结果已被移除

复制代码

使用 lru_cache 装饰器，可以轻松为函数添加缓存功能，而且不须要手动管理缓存的逻辑。maxsize 参数指定了缓存的最大容量。