我用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(30))
print(fib.cache_info())
输出为
CacheInfo(hits=28, misses=31, maxsize=8, currsize=8)个
我知道未命中的次数是31(fib(0)，...fib(30))
但点击量应该是58次.例如，fib(2)应该对fib(0)和fib(1)命中，而对fib(2)命中.因此，每个呼叫都会产生一次未命中和两次命中.
我试着在网上搜索，但没有得到多少相关的结果.
但点击量应该是58次.
不要忘记，当命中时，递归停止.
当计算fib(n-1) + fib(n-2)时，fib(n-2)调用将立即命中，因为fib(n-1)已经确保它被缓存，因此fib(n-2)调用中不会出现进一步的递归(也不是命中).唯一的例外是当第二个项是f(0)时:第一个项没有计算f(0)，因为1被认为是基本情况，所以在这里正确的项仍然表示未命中且没有命中.
但一般原则(忽略例外)在递归的每个级别上都是正确的:这个和的第二项只会命中一次，其他什么都不会.那里没有递归.唯一的递归发生在第一项的求值时.
f(5)年的可视化:
miss __f(5)__
/ \
miss __f(4)__ f(3) hit
/ \
miss __f(3)__ f(2) hit
/ \
miss __f(2)__ f(1) hit
/ \
miss f(1) f(0) miss (the exception)
| |
base base
因此，对于f(5)，我们有6(=n+1)个未命中和3(=n-2)个命中.将这个推理应用于f(30)，你就得到了报告的结果.
注意:缓存需要至少保留three个最近访问的结果.因此，即使您使用@lru_cache(maxsize=3)，您也会得到相同的命中和未命中计数.当 Select 小于3的值时，缓存将变得无用.