2

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

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 值，我如何才能使这种类型的解决方案足够快地工作？

4

2 回答 2

5

您的函数没有被记忆（至少不是有效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)
于 2020-05-05T02:36:52.360 回答
2

你很近。“备忘录”的重点是保存调用，但无论参数的结果是否已被记住，您都在进行递归调用。所以你实际上并没有节省调用的工作。最简单的就是在函数外定义缓存，如果参数在缓存中就直接返回：

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 层才能找到已经存储在缓存中的参数。我想我会提到这一点，因为在回答“备忘录”问题时几乎没有人这样做。但实际上，备忘录不仅可以极大地加快某些递归算法的速度，而且还可以将它们应用于“递归太深”的一些问题，而无需构建备忘录来限制最大调用深度。

于 2020-05-05T02:52:04.883 回答