Python中的斐波那契函数记忆

Question

我正在研究codewars中的一个问题，希望您记住斐波那契数列。到目前为止，我的解决方案是：

def fibonacci(n):  
    return fibonacci_helper(n, dict())

def fibonacci_helper(n, fib_nums):
    if n in [0, 1]:
        return fib_nums.setdefault(n, n)

    fib1 = fib_nums.setdefault(n - 1, fibonacci_helper(n - 1, fib_nums))
    fib2 = fib_nums.setdefault(n - 2, fibonacci_helper(n - 2, fib_nums))

    return fib_nums.setdefault(n, fib1 + fib2)

对于较小的n值，它工作得很好，但是会大大降低，直到超过30个标记，这让我感到奇怪-这个解决方案是否还被记住？对于大的n值，我如何使这种类型的解决方案足够快地工作？

Answer 1

您的函数没有被记忆（至少没有有效地记忆），因为无论您是否已经有记忆的值，您都调用fibonacci_helper。这是因为setdefault不会做任何魔术，以防止在将参数传递给函数之前对其进行求值-您在dict检查其是否包含值之前进行了递归调用。

记住点要小心，避免在您已经知道答案的情况下进行计算（在这种情况下为冗长的递归调用）。

解决此实现的方法将类似于：

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)