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)

Answer 2

你很接近。 "a memo" 的目的是保存调用，但是无论参数的结果是否已经被记住，你都在进行递归调用。所以你实际上并没有节省调用的工作。最简单的是在函数外定义缓存，如果参数在缓存中就直接return：

fib_cache = {0 : 0, 1 : 1}

def fib(n):
    if n in fib_cache:
        return fib_cache[n]
    fib_cache[n] = result = fib(n-1) + fib(n-2)
    return result

然后缓存也将在顶级调用中持续存在。

但现在还有另一个问题 ;-) 如果参数足够大（比如 30000），您可能会得到 RecursionError（递归调用的级别太多）。这不是因为使用了缓存，它只是非常深的递归所固有的。

您也可以绕过这个问题，方法是首先利用缓存调用较小的参数，然后逐步调用实际参数。例如，在 if 块之后插入：

    for i in range(100, n, 100):
        fib(i)

这确保了递归永远不必超过 100 级深度来查找已存储在缓存中的参数。我想我会提到这一点，因为在回答 "memo" 问题时几乎没有人会这样做。但备忘录实际上不仅可以大大加快某些递归算法的速度，而且还可以将它们应用于一些"recurse too deep"没有构造备忘录以限制最大调用深度的问题。

Python 中的斐波那契函数记忆

Fibonacci Function Memoization in Python

python

fibonacci

memoization