使用动态规划计算斐波那契命中数

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(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) 给出未命中。因此，每次调用都会产生一次未命中和两次命中。

我尝试在互联网上搜索，但没有得到太多相关结果。

Answer 1

但是点击数应该是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)

，你就会得到报告的结果。