python中的Memos (想想Python练习11.6)

Question

在“思考Python”第11章中，Allen提到“.存储以供以后使用的以前计算的值称为备忘录”(第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

known[res] = n

是必需的，否则您将不会将结果存储在“已知”中，而且每次都需要重新计算进展的所有元素。

如果以已知= {0:0，1:1}开头，则在fibonacci(29)已知之后将填充：

{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)都在已知的中。

Answer 2

你做了个错字。这本书的代码是：

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，则需要更改递归调用，也是如此。否则，回忆录版本被称为非回忆录版本，而你却得不到任何好处。