使用functools.lru_cache实现斐波那契时的缓存命中数疑问

先看你的代码和输出：

@lru_cache(maxsize=8)
def fib(n):
    if n <2:
        return n
    else:
        return fib(n-1) + fib(n-2)
print(fib(8))
print(fib.cache_info())
for i in range(9, 12):
    fib(i)
    print(fib.cache_info())

输出：

21
CacheInfo(hits=6, misses=9, maxsize=8, currsize=8)
CacheInfo(hits=8, misses=10, maxsize=8, currsize=8)
CacheInfo(hits=10, misses=11, maxsize=8, currsize=8)
CacheInfo(hits=12, misses=12, maxsize=8, currsize=8)

核心疑问解答 #

你误以为调用fib(9)会触发fib(2)到fib(8)的7次命中，这是对记忆化逻辑的误解——缓存的作用是直接返回已计算过的结果，不会重新触发递归链。

当你调用fib(9)时，实际执行流程是：

1. fib(9)不在缓存中，产生1次未命中（misses从9→10）。
2. 计算fib(9)需要fib(8)+fib(7)：
   • fib(8)已经在缓存中（之前调用fib(8)时已存入），触发1次命中。
   • fib(7)也在缓存中（属于最近8个被访问的条目，未被LRU淘汰），触发1次命中。
3. 计算完成后，fib(9)被存入缓存，此时缓存已满（maxsize=8），LRU会淘汰最久未使用的条目（比如fib(0)或fib(1)，取决于访问顺序），但这对本次命中数无影响。

所以fib(9)调用后，命中数从6增加到8（+2），完全符合输出。

同理：

• 调用fib(10)时，需要fib(9)+fib(8)，两者都在缓存中，触发2次命中（hits从8→10），加上fib(10)的1次未命中（misses从10→11）。
• 调用fib(11)时，需要fib(10)+fib(9)，两者都在缓存中，触发2次命中（hits从10→12），加上fib(11)的1次未命中（misses从11→12）。

关于fib(8)的命中数解释 #

调用fib(8)时的6次命中来自递归过程中重复访问已缓存的条目：
比如计算fib(3)时，fib(2)和fib(1)已缓存；计算fib(4)时，fib(3)和fib(2)已缓存；直到计算fib(7)时，fib(6)和fib(5)已缓存——这些重复访问累计产生6次命中，加上9次未命中（对应fib(0)到fib(8)首次调用），最终得到CacheInfo(hits=6, misses=9)。

总结 #

maxsize=8确实会导致旧条目被淘汰，但在你这个场景中，每次计算新的斐波那契数时，只需要依赖最近的两个已缓存值，这两个值始终在缓存中（属于最近访问的条目，不会被LRU淘汰），所以每次新调用都会固定产生2次命中、1次未命中。

内容的提问来源于stack exchange，提问作者user23359931