什么是记忆化以及如何在 Python 中使用它? [英] What is memoization and how can I use it in Python?

问题描述

我刚开始使用 Python，我不知道 memoization 是什么以及如何使用它.另外，我可以举个简单的例子吗?

I just started Python and I've got no idea what memoization is and how to use it. Also, may I have a simplified example?

推荐答案

Memoization 有效地是指根据方法输入记住(备忘录"→备忘录"→要记住)方法调用的结果，然后返回记住的结果而不是再次计算结果.您可以将其视为方法结果的缓存.有关更多详细信息，请参阅 算法简介 (3e)，Cormen 等人

Memoization effectively refers to remembering ("memoization" → "memorandum" → to be remembered) results of method calls based on the method inputs and then returning the remembered result rather than computing the result again. You can think of it as a cache for method results. For further details, see page 387 for the definition in Introduction To Algorithms (3e), Cormen et al.

在 Python 中使用 memoization 计算阶乘的简单示例如下所示:

A simple example for computing factorials using memoization in Python would be something like this:

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]

你可以变得更复杂，把记忆过程封装成一个类:

You can get more complicated and encapsulate the memoization process into a class:

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"的功能允许您现在简单地编写以下内容来完成相同的事情:

A feature known as "decorators" was added in Python 2.4 which allow you to now simply write the following to accomplish the same thing:

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

Python 装饰器库 有一个类似的装饰器，名为 memoized 比此处显示的 Memoize 类稍微强一些.

The Python Decorator Library has a similar decorator called memoized that is slightly more robust than the Memoize class shown here.

这篇关于什么是记忆化以及如何在 Python 中使用它?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！