为什么字典在函数中时我的斐波那契要花这么长时间？

Question

这里我有一些代码可以返回斐波那契数字的最后一位。当我将缓存字典放置在函数中时，程序对于小n正常工作。当我尝试更大的n（例如300）时，该程序将永远耗费时间。但是，当我使字典成为全局字典时，我会得到一个较大的n（例如300）的即时结果。是什么导致在函数中声明的字典与函数外部声明的字典之间如此大的性能差异？

def fib_last_digit_mem(n):
    cache = {}

    if n in cache:
        return cache[n]

    if(n <= 1):
        return n

    fib = (fib_last_digit_mem(n-1) + fib_last_digit_mem(n-2))%10
    cache[n] = fib
    return fib

Answer 1

由于这是一个递归函数，如果您实例化函数内部的缓存，则每次函数递归时都会再次实例化它。这也意味着缓存始终为空，因此您永远不会走短路if n in cache

Answer 2

您实际上并没有缓存任何东西，因为local var cache每次调用该函数时都会初始化为一个空dict。当然，一旦计算出值，就将其添加到字典中。但是然后您返回：cache超出范围，并且dict被垃圾回收。

您需要对存在于[[outside cache中的fib_last_digit_mem的某些引用，但这不一定是全局变量。

考虑：

def make_cached_fib():
    cache = {}
    def _(n):
        if n in cache:
            return cache[n]
        if n <= 1:
            return n
        fib = (_(n-1) + _(n-2)) % 10
        cache[n] = fib
        return fib
    return _

fib_last_digit_mem = make_cached_fib()

这里，缓存不是全局的；在定义fib_last_digit_mem的范围内。一旦make_cached_fib返回，对缓存的唯一引用就是fib_last_digit_mem本身持有的那个。

Answer 3

您在递归调用的函数中实例化缓存。这导致两个问题：

1）每次进行递归调用时，都必须实例化一个性能会有所下降的缓存，但是该创建过程并不是代码运行缓慢的原因。

2）真正的原因，甚至更大的问题是，您不对缓存执行任何操作。动态编程使您可以重用以前计算的结果，因此您不必再次计算它们。您将这些结果保存在缓存中。但是因为您每次调用该方法都会使缓存实例化，所以所有递归调用最终都会拥有一个自己的空本地缓存，而不是共享一个全局缓存，这有助于您避免再次计算先前计算出的结果。

示例：

如果您全局声明缓存并计算fibonacci(10)，则最后一个操作只需从缓存中获取fibonacci(9)的结果，然后向其添加另一个数字。它是计算下一个第n个斐波那契数的唯一加法。在您的情况下，您不仅要获取fibonacci(9)的结果并添加一个数字，还要实际计算fibonacci(9)，这意味着您必须再次计算fibonacci(8)，以此类推。编程（全局缓存）