python中的记忆斐波那契算法

Question

我有这种记忆技术来减少获取斐波那契序列号的调用次数：

def fastFib(n, memo):
    global numCalls
    numCalls += 1
    print 'fib1 called with', n
    if not n in memo:
        memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
        return memo[n]


def fib1(n):
    memo = {0:1, 1:1}
    return fastFib(n, memo)


numCalls = 0
n = 6
res = fib1(n)
print 'fib of', n,'=', res, 'numCalls = ', numCalls

但我被困在这里：memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)和这里memo = {0:1, 1:1}。每次我想获得一个号码的 fib 时，它是如何准确减少呼叫次数的？

Answer 1

您应该memo[n]始终返回，而不仅仅是在不连续查找时返回（最后一行fastFib()）：

def fastFib(n, memo):
    global numCalls
    numCalls += 1
    print 'fib1 called with', n
    if not n in memo:
        memo[n] = fastFib(n-1, memo) + fastFib(n-2, memo)
    #this should be outside of the if clause:
    return memo[n] #<<<<<< THIS

通过这种方式减少了调用次数，因为对于n您实际计算和递归的每个值至多一次，限制对O(n)（2n调用上限）的递归调用次数，而不是一遍又一遍地重新计算相同的值，有效进行指数数量的递归调用。

fib(5) 的一个小例子，其中每一行都是一个递归调用：

幼稚的方法：

f(5) = 
f(4) + f(3) = 
f(3) + f(2) + f(3) =
f(2) + f(1) + f(2) + f(3) =
f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) = 
1 + f(0) + f(1) + f(2) + f(3) = 
2 + f(1) + f(2) + f(3) =
3 + f(2) + f(3) = 
3 + f(1) + f(0) + f(3) = 
3 + 1 + f(0) + f(3) = 
5 + f(3) = 
5 + f(2) + f(1)  =
5 + f(1) + f(0) + f(1) =
5 + 1 + f(0) + f(1) =
5 + 2 + f(1) =
8

现在，如果你使用记忆化，你不需要重新计算很多东西（比如f(2)，计算了 3 次），你会得到：

f(5) = 
f(4) + f(3) = 
f(3) + f(2) + f(3) =
f(2) + f(1) + f(2) + f(3) =
f(1) + f(0) + f(1) + f(2) + f(3) = (base clauses) = 
1 + f(0) + f(1) + f(2) + f(3) = 
2 + f(1) + f(2) + f(3) =
3 + f(2) + f(3) =  {f(2) is already known}
3 + 2 + f(3) = {f(3) is already known}
5 + 3  = 
8

如您所见，第二个比第一个短，并且数字 ( n)越大，这种差异就越显着。

Answer 2

可以使用Python 3.2+ 中的functools库来完成

import functools

@functools.lru_cache(maxsize=None) #128 by default
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)