Naive递归比Memoized递归更快

Question

我是python的初学者，观看此视频是为了学习动态编程。对于寻找斐波那契级数的情况，导师引入了记忆来提高递归算法的性能。完整的代码如下

import time
def fibonacci1(n):
'''This uses the naive fibonacci algorithm. '''
if n < 2:
return n
else:
return fibonacci1(n-1) + fibonacci1(n-2)
def fibonacci2(n):
''' This function uses a memo of computed values to speed up the process'''
memo = {}
if n in memo:
return memo[n]
if n < 2:
return n
f = fibonacci2(n-1) + fibonacci2(n-2)
memo[n] = f
return f
def screen(i,N):
if i==1:
return fibonacci1(N)
if i == 2:
return fibonacci2(N)
N = int(input("Enter a number: "))
for i in range(2):
t0 = time.time()
fib = screen(i+1,N)
print("The "+ str(N) +"th fibonacci number is {}".format(fib))
t1 = time.time()
print("Time taken is : {}s".format(t1-t0))

但这是我收到的输出：斐波那契输出

有人能帮我吗？

Answer 1

这里发生的情况是，您的memo是一个局部变量，在每次运行fibonacci2时，您都会将一个空dict分配给它。因此，您永远不会在memo中找到n。

有多种方法可以实现你想要做的事情。其中一种(不是最棒的，但至少很容易理解(是使用全局变量：

memo = {}
def fibonacci2(n):
''' This function uses a memo of computed values to speed up the process'''
global memo
if n in memo:
return memo[n]
if n < 2:
return n
f = fibonacci2(n-1) + fibonacci2(n-2)
memo[n] = f
return f

这里我们在函数之外定义了memo，所以它只定义了一次。global memo行表示我们在函数中使用的memo实际上是在它之外定义的

Answer 2

从您的代码：

memo = {}
if n in memo:

n怎么可能在您之前创建的dict中为空？

我会这样做：

def fibonacci2(n, memo={}):
...

Answer 3

每次调用fibonacci2时，它似乎都会将memo重置为空字典。因此，它增加了一些dict读写的开销，但实际上并没有给算法增加记忆。如果只将memo = {}向上移动几行，使其值持久化，这似乎会有很大帮助。

Answer 4

将fibonacci2(n)函数外的memo = {}声明为全局变量，因为当您在fibonacci2()内部声明memo时，当函数调用时，它将始终初始化为空。你可以这样做

memo = {}
def fibonacci2(n):
''' This function uses a memo of computed values to speed up the process'''

if n in memo:
return memo[n]
if n < 2:
return n
f = fibonacci2(n-1) + fibonacci2(n-2)
memo[n] = f
return f