什么是记忆化以及如何在 Python 中使用它？

Question

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

原文由 blur959 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

记忆化实际上是指根据方法输入记住（“记忆化”→“备忘录”→被记忆）方法调用的结果，然后返回记忆的结果而不是再次计算结果。您可以将其视为方法结果的缓存。有关更多详细信息，请参阅第 387 页，了解 算法简介(3e) 中的定义，Cormen 等人。

在 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)

Python 装饰器库 有一个名为 memoized 的类似装饰器，它比这里显示的 Memoize 类稍微更健壮。

原文由 jason 发布，翻译遵循 CC BY-SA 3.0 许可协议