有记忆功能的斐波那契数在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，那么一切都能正常工作，fine...anyone知道原因吗？谢谢!

Answer 1

fib递归到fib中，而不是fib1中。如果记忆版本有一个不同的名称，它将不会被使用。

Answer 2

在该代码中，fib是非记忆函数的名称。fib1是您为memoized函数指定的名称。但是，如果您看到您的代码，您将看到它递归地调用非记忆版本的fib。这就是为什么你没有获得速度优势的原因。

Answer 3

我同意添加一些指纹，您可能会看到问题。你已经非常接近实际得到它了。

您现在拥有的只存储n，其中n是提供给fib1的参数。在fib内部，你调用fib，它不会记录任何先前计算的值。因此，通过将打印语句添加到fib print "fib ", n并调用fib1(4)，您将获得以下输出：

fib 4

图2

图3

图1

fib 2

所以你可以看到它用n=2调用了fib两次。fib更快的原因是因为它实际上是fib = memo(fib)，因为你将fib重新定义为memoized函数。