带记忆功能的Fibonacci数字在Python中运行缓慢？

Question

def fib(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    return fib(n-2) + fib(n-1)


def memo(f):
    cache = {}
    def memoized(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return memoized

fib1 = memo(fib)

这段代码在我的笔记本上运行得很慢， 但是如果我把fib1改成fib，那么一切都很好…有人知道原因吗？谢谢！在

Answer 1

我同意添加一些指纹你可能会发现问题。你很快就要得到它了。在

你现在只存储n，其中n是fib1的参数。在fib中，调用fib，它不会存储任何以前计算的值。因此，通过向fibprint "fib ", n添加print语句并调用fib1（4），您将得到以下输出：

fib 4
fib 2
fib 3
fib 1
fib 2

所以你看到它用n=2调用fib两次。之所以fib = memo(fib)更快，是因为它实际上是momolizing，因为您将fib重新定义为记忆函数。在