使用 lru_cache 斐波那契命中数

Question

我正在使用 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())`

输出为：

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(8) 中的未命中次数为 8 (fib(0),...fib(8)) 以及所有后续调用中的未命中次数。但我不清楚 fib(9)、fib(10)、fib(11) 中的命中数。如果我理解正确的话，在 fib(9) 中，命中将是 fib(2)...fib(8)。那么，点击次数将为 7。是因为最大大小=8 吗？

Answer 1

不，这不是因为缓存的最大大小（您会得到与

max_size=3

相同的结果）。您获得这些统计数据是因为您在循环之前已经调用了

fib(9)

，从而使对

fib(8)

的调用变得更轻松：

如果您在循环之前没有调用

fib(8)

，那么在循环的第一次迭代中，统计数据中的命中数将会减少。这是预料之中的。

在您的版本中，您总共又对

fib(8)

进行了一次调用：当您拨打

fib(9)

时，

fib(8)

会计算一次额外的点击，而如果您之前没有进行

fib(8)

的话，循环，那么当调用

fib(9)

时它就不是命中。

当您进入循环的下一次迭代时，这种效果是类似的：由于上一次迭代已经缓存了少一个参数的结果，因此当前调用将在其第一次递归调用中命中。