python - Python 中的备忘录(Think 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')添加到字典(备忘录)中。

如果我在 fibonacci 的任何调用之后打印字典，字典只包含之前存在的信息 (0:0, 1:1) 以及 n 的信息:

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

因此没有保存可能有助于节省时间的中间结果(备忘录)。使用时间模块，我只能获得 memoized_fibonacci 函数相对于更简单的 fibonacci 函数的最小时间优势。 (即对于 memoized_fibonacci(40) 我需要 58.1 秒，对于 fibonacci(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)，您还需要更改递归调用。否则，已内存的版本正在调用未内存的版本，您不会获得任何好处。