Python 中的斐波那契函数记忆

Question

我正在解决一个问题代码战争中的一个问题，希望你记住斐波那契数列。到目前为止我的解决方案是：

\n\n\n\n

def fibonacci(n):  \n    return fibonacci_helper(n, dict())\n\ndef fibonacci_helper(n, fib_nums):\n    if n in [0, 1]:\n        return fib_nums.setdefault(n, n)\n\n    fib1 = fib_nums.setdefault(n - 1, fibonacci_helper(n - 1, fib_nums))\n    fib2 = fib_nums.setdefault(n - 2, fibonacci_helper(n - 2, fib_nums))\n\n    return fib_nums.setdefault(n, fib1 + fib2)\n

\n\n

对于较小的 n 值，它工作得相当好，但超过 30 标记时速度明显减慢，这让我想知道 \xe2\x80\x94 这个解决方案是否已被记忆？对于较大的 n 值，如何让这种类型的解决方案足够快地工作？

\n

Answer 1

您的函数不会被记忆（至少不会有效），因为fibonacci_helper无论您是否已经具有记忆值，您都会调用。这是因为setdefault在将参数传递到函数之前不会执行任何阻止对参数进行求值的魔法 - 您在字典检查它是否包含该值之前进行递归调用。

记忆的要点是要小心避免在您已经知道答案的情况下进行计算（在本例中是冗长的递归调用）。

修复此实现的方法类似于：

def fibonacci(n):  
    return fibonacci_helper(n, {0: 0, 1: 1})

def fibonacci_helper(n, fib_nums):
    if n not in fib_nums:
        fib1 = fibonacci_helper(n-1, fib_nums)
        fib2 = fibonacci_helper(n-2, fib_nums)
        fib_nums[n] = fib1 + fib2
    return fib_nums[n]

如果您被允许不重新发明轮子，您也可以只使用functools.lru_cache，它通过装饰器的魔力为任何函数添加记忆：

from functools import lru_cache

@lru_cache
def fibonacci(n):
    if n in {0, 1}:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

您会发现，即使对于非常高的值，这也非常快：

>>> fibonacci(300)
222232244629420445529739893461909967206666939096499764990979600

但是如果您定义完全相同的函数而不使用它，@lru_cache它会变得非常慢，因为它没有从缓存中受益。

>>> fibonacci(300)
(very very long wait)