什么是备忘录模式，我如何在Python中使用它？

Question

我刚开始学习Python，完全不知道什么是备忘录，也不知道怎么用。能给我一个简单的例子吗？

Answer 1

其他回答已经很好地解释了这是什么，我就不重复了。这里有一些可能对你有用的要点。

通常，记忆化是一种可以应用于任何计算某些（比较耗费资源的）东西并返回值的函数的操作。因此，它通常被实现为一个装饰器。实现起来很简单，基本上就是这样的：

memoised_function = memoise(actual_function)

或者可以用装饰器的方式来表示：

@memoise
def actual_function(arg1, arg2):
   #body

Answer 2

functools.cache 装饰器：

Python 3.9 新增了一个功能 functools.cache。它会把用特定参数调用的函数结果存储在内存中，这个过程叫做记忆化。使用起来非常简单：

import functools
import time

@functools.cache
def calculate_double(num):
    time.sleep(1) # sleep for 1 second to simulate a slow calculation
    return num * 2

第一次你调用 caculate_double(5) 时，可能需要一秒钟，返回结果是10。第二次你用同样的参数 calculate_double(5) 调用这个函数时，它会立刻返回10。

加上 cache 装饰器后，如果这个函数最近已经用某个值调用过，它就不会重新计算这个值，而是直接使用之前缓存的结果。这样做可以大大提高速度，同时代码也不会因为缓存的细节而变得复杂。

(编辑：之前的例子是用递归计算斐波那契数，但我换成了这个例子以避免混淆，所以之前的评论可能不太适用。)

functools.lru_cache 装饰器：

如果你需要支持旧版本的 Python，functools.lru_cache 在 Python 3.2 及以上版本都可以使用。默认情况下，它只会缓存最近使用的128次调用，但你可以把 maxsize 设置为 None，表示缓存永远不会过期：

@functools.lru_cache(maxsize=None)
def calculate_double(num):
    # etc

---

Answer 3

记忆化（Memoization）其实就是记住方法调用的结果。简单来说，就是根据输入的不同，保存下计算结果，下次再遇到相同的输入时，就直接拿出之前保存的结果，而不是重新计算。你可以把它想象成一个存储方法结果的缓存。想了解更多，可以查看Introduction To Algorithms（第三版）第387页的定义。

下面是一个用记忆化计算阶乘的简单例子，使用的是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中，增加了一个叫做“装饰器”（decorators）的功能，这样你就可以简单地写下面的代码来实现同样的效果：

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

还有一个类似的装饰器，叫做memoized，它在Python装饰器库中，功能比这里展示的Memoize类更强大一些。