朴素递归比记忆递归更快

Question

我是 python 的初学者，正在观看 this 学习动态规划的视频。对于找斐波那契数列的案例，导师引入了memoization来提高递归算法的性能。完整代码如下

    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))

但这是我收到的输出： FibonacciOutput

有人可以帮我解决这个问题吗？

Answer 1

这里发生的是你的 memo 是一个局部变量，你在 fibonacci2 的每个运行的开头分配了一个空字典。因此，您永远不会在 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

看起来它每次调用 fibonacci2 时都会将 memo 重置为空字典。所以它增加了一些执行 dict 读写的开销，但实际上并没有将记忆添加到算法中。如果您只是将 memo = {} 向上移动几行以使其值保持不变，这似乎有很大帮助。

Answer 3

来自您的代码：

    memo = {}
    if n in memo:

n怎么可能在你之前创建的空字典中？

我会这样做：

def fibonacci2(n, 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

朴素递归比记忆递归更快

Naive Recursion faster then Memoized recursion

python

recursion

optimization

dynamic-programming

memoization