Python-什么是备忘录，如何在Python中使用备忘录？

Question

我刚开始使用Python，却不知道什么是记忆以及如何使用它。另外，我可以举一个简化的例子吗？

Answer 1

记忆有效地指基于方法输入记忆方法调用的结果（“记忆”→“备忘录”→要记忆），然后返回记忆的结果，而不是再次计算结果。你可以将其视为方法结果的缓存。有关更多详细信息，请参见第387页的Cormen等人的《算法简介》（3e）中的定义。

一个简单的示例，使用Python中的记忆来计算阶乘是这样的：

factorial_memo = {}
def factorial(k):
    if k < 2: return 1
    if k not in factorial_memo:
        factorial_memo[k] = k * factorial(k-1)
    return factorial_memo[k]

你可能会变得更加复杂，并将备注过程封装到一个类中：

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        #Warning: You may wish to do a deepcopy here if returning objects
        return self.memo[args]

然后：

def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

factorial = Memoize(factorial)

Python 2.4中添加了一个称为“ 装饰器 ”的功能，使你现在只需编写以下代码即可完成同一操作：

@Memoize
def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

Answer 2

是Python 3.2的新功能functools.lru_cache。默认情况下，它仅缓存最近使用的128个调用，但是你可以将设置为maxsize，None以指示缓存永不过期：

import functools

@functools.lru_cache(maxsize=None)
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

此功能本身非常慢，请尝试fib(36)，你将需要等待大约十秒钟。

添加lru_cache注释可确保如果最近已为特定值调用了该函数，则不会重新计算该值，而是使用缓存的先前结果。在这种情况下，它可以极大地提高速度，而代码不会因缓存的细节而混乱。