python 中的备忘录（思考 Python 练习 11.6）

Question

在 Think Python 一书的第 11 章中，Allen Downey 提到“...存储供以后使用的先前计算的值称为 memo” （第 107 页）。

然后重写以下函数以使用 memos 改进它：

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

重写后的函数如下所示：

known = {0: 0, 1: 1}

def memoized_fibonacci(n):
    if n in known:
        return known[n]
    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    return res

我想知道，为什么有必要在返回之前将递归调用（此处：'res'）添加到字典（备忘录）中。

如果我在斐波那契的任何调用之后打印字典，字典只包含之前存在的信息 (0:0, 1:1) 以及 n:[=18= 的信息]

>> memoized_fibonacci(7)
>> print known
>> {0: 0, 1: 1, 7: 13}

因此没有保存可能有助于节省时间的中间结果（备忘录）。使用时间模块，我只能获得 memoized_fibonacci 函数相对于更简单的斐波那契函数的最小时间优势。（即对于 memoized_fibonacci(40) 我需要 58.1 秒，对于斐波那契数（40）我需要 58.8 秒）

删除 known[n] = res 调用也不会降低记忆函数的速度。

known = {0: 0, 1: 1}

def memoized_fibonacci(n):
    if n in known:
        return known[n]
    return fibonacci(n-1) + fibonacci(n-2)    # Not slower!

我是不是漏掉了重点？有人可以向我解释一下，为什么调用 known[n] = res 很重要吗？谢谢！

Answer 1

你打错了。来自 the book 的代码是：

known = {0:0, 1:1}

def fibonacci(n):
    if n in known:
        return known[n]

    res = fibonacci(n-1) + fibonacci(n-2)  # note same name
    known[n] = res
    return res

如果您重命名函数（memoized_fibonacci），您还需要更改递归调用。否则，记忆版本正在调用非记忆版本，你不会得到任何好处。

Answer 2

known[res] = n

是必需的，否则您不会将结果存储在 "known" 中，并且每次都需要重新计算级数的所有元素。

如果您从 known = {0:0, 1:1} 开始，在 fibonacci(29) known 之后将填充：

{0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55, 11: 89, 12: 144, 13: 233, 14: 377, 15: 610, 16: 987, 17: 1597, 18: 2584, 19: 4181, 20: 6765, 21: 10946, 22: 17711, 23: 28657, 24: 46368, 25: 75025, 26: 121393, 27: 196418, 28: 317811, 29: 514229}

然后移动到 fibonacci(30) 几乎是瞬间的，因为 fibonacci(29) 和 fibonacci(28) 都在 known.

python 中的备忘录（思考 Python 练习 11.6）

Memos in python (Think Python exercise 11.6)

python

dictionary

memoization

fibonacci