什么是记忆化，我如何在Python中使用它？

Question

我刚刚开始学习Python，对于“记忆化”的概念和使用方法一无所知。能否给出一个简单的示例呢？

- blur959

---

当相关维基百科文章的第二个句子包含“在一般自顶向下的解析算法中相互递归地进行下降解析[1]，并在多项式时间和空间内处理模糊性和左递归[2][3]”这一短语时，我认为向SO询问正在发生什么是完全合适的。 - Clueless

@Clueless：该短语前面有“记忆化也被用于其他情境（并非仅为了提高速度），例如”。因此，这只是一些例子的列表（无需理解）；它不是关于记忆化解释的一部分。 - ShreevatsaR

由于pycogsci.info已经关闭，这里提供一个新的PDF文件链接：http://people.ucsc.edu/~abrsvn/NLTK_parsing_demos.pdf - Stefan Gruenwald

看到有多少人回答并仍在回答这个问题，让我相信了“自行车棚效应”https://en.wikipedia.org/wiki/Law_of_triviality。 - A_P

@A_P 实际上，在你写这篇文章的时候，除了一个答案是最近的（2016年），其他13个答案都是5年前的（2014年）。不确定这是否算作“仍在回答”。我刚刚发布的答案增加了速度考虑因素，而其他答案中我没有看到这些因素，并且并未实现新的方法或任何东西。当然有你所描述的现象的例子，但我不确定这是否就是它。 - Luc

Answer 1

记忆化实际上指的是基于方法输入来记住（"memoization" → "memorandum" → 被记住）方法调用的结果，然后返回记住的结果而不是再次计算结果。你可以把它看作是一种方法结果的缓存。有关详细信息，请参见Cormen等人所著《算法导论》（第3版）第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中添加了一个名为"装饰器"的特性，它使您现在可以简单地编写以下内容来完成相同的事情：

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

Python装饰器库中有一个类似的装饰器叫做memoized，比这里展示的Memoize类稍微更加强大一些。

- jason

---

Memoize类的解决方案存在缺陷，它与factorial_memo的工作方式不同，因为def factorial内部的factorial仍然调用旧的未记忆化的factorial。 - adamsmith

我认为@dlutxx说得有道理。第一版可以快速计算出第50个斐波那契数列第一次计算，而使用Memoize的第二版则不能。 - JohnJamesSmith0

顺便提一句，你也可以写成if k not in factorial_memo:，这比if not k in factorial_memo:更易读。 - ShreevatsaR

应该将这个功能设计为装饰器。 - Emlyn O'Regan

我知道这是一条旧评论，但 args 是元组。def some_function(*args) 会使 args 成为一个元组。 - Adam Smith

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，则{{link1：functools.lru_cache}}适用于Python 3.2+。默认情况下，它仅缓存最近使用的128个调用，但您可以将maxsize设置为None，以指示缓存永远不会过期：

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

---

- Flimm

---

尝试执行fib(1000)，出现了RecursionError: maximum recursion depth exceeded in comparison。 - Andreas K.

Python 3的默认递归限制是1000。第一次调用fib函数时，需要递归到基本情况之前才能进行记忆化。因此，你目前的行为基本上是可以预期的。 - Quelklef

如果我没记错的话，它只会在进程未被终止时缓存，对吗？或者无论进程是否被终止，它都会缓存吗？比如说，如果我重新启动系统，缓存的结果还会被缓存吗？ - Kristada673

请注意，由于这是一个递归函数并且缓存了自己的中间结果，因此甚至加速了该函数的第一次运行。也许最好示例一个本质上很慢的非递归函数，以便更清楚地向像我这样的菜鸟展示。 :D - endolith

3.9 版本中新增了 functools.cache，它至少在 cpython 中是 lru_cache(maxsize=None) 的一个包装器，但名称更短。 - Amndeep7

Answer 3

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

通常，记忆化会应用于计算某些（昂贵的）值并返回结果的函数。因此，通常将其实现为一个装饰器。其实现非常简单，类似于以下代码：

memoised_function = memoise(actual_function)

或者表达为装饰器

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

- Noufal Ibrahim

Answer 4

我发现这非常有用。

from functools import wraps


def memoize(function):    
    memo = {}
        
    @wraps(function)
    def wrapper(*args):

        # add the new key to dict if it doesn't exist already  
        if args not in memo:
            memo[args] = function(*args)

        return memo[args]

    return wrapper
    
    
@memoize
def fibonacci(n):
    if n < 2: return n
    return fibonacci(n - 1) + fibonacci(n - 2)
    
fibonacci(25)

- mr.bjerre

---

请参阅 https://docs.python.org/3/library/functools.html#functools.wraps 了解为什么应该使用 functools.wraps。 - anishpatel

我需要手动清除“memo”以释放内存吗？ - nos

整个想法是将结果存储在会话内的备忘录中。也就是说，它不会被清除。 - mr.bjerre

“args not in memo”是在逐个列举memo键列表并检查args是否匹配吗？还是实际上是使用底层字典并检查哈希（args）的条目是否存在于memo字典的底层数组中？如果是前者，那么如果我们使用defaultdictionaries来坚持检查哈希，这段代码会运行得更快吗？ - undefined

Answer 5

记忆化是指保留昂贵计算的结果，而不是不断重新计算它，并返回已缓存的结果。

以下是一个例子：

def doSomeExpensiveCalculation(self, input):
    if input not in self.cache:
        <do expensive calculation>
        self.cache[input] = result
    return self.cache[input]

有关记忆化的更完整描述可以在维基百科的记忆化条目中找到。

- Bryan Oakley

Answer 6

不要忘记内置的hasattr函数，对于那些想手工制作的人来说非常有用。这样您就可以将 mem 缓存保留在函数定义内部（而不是全局）。

def fact(n):
    if not hasattr(fact, 'mem'):
        fact.mem = {1: 1}
    if not n in fact.mem:
        fact.mem[n] = n * fact(n - 1)
    return fact.mem[n]

- Karel Kubat

---

这似乎是一个非常昂贵的想法。对于每个n，它不仅缓存n的结果，还缓存2 ... n-1的结果。 - codeforester

Answer 7

记忆化是指在递归算法中保存过去操作的结果，以减少如果稍后需要进行相同计算，则无需遍历递归树。

参见http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/

Python中的Fibonacci记忆化示例：

fibcache = {}
def fib(num):
    if num in fibcache:
        return fibcache[num]
    else:
        fibcache[num] = num if num < 2 else fib(num-1) + fib(num-2)
        return fibcache[num]

- Romaine Carter

---

为了提高性能，可以使用前几个已知的值预先填充斐波那契缓存(fibcache)，这样就可以将处理它们的额外逻辑从代码的“热路径”中分离出来。 - jkflying

Answer 8

记忆化是将函数转换为数据结构的过程。通常情况下，我们希望这种转换是增量且延迟的（按需对给定的域元素或“键”进行转换）。在惰性函数语言中，这种延迟转换可以自动发生，因此可以实现记忆化而不需要（显式）副作用。

- Conal

Answer 9

首先，我应该回答第一个问题：什么是记忆化？

它只是一种用内存换时间的方法。想想乘法表。

在Python中，使用可变对象作为默认值通常被认为是不好的。但是，如果明智地使用，它实际上可以用来实现记忆化。

这里有一个例子，改编自http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects

在函数定义中使用可变的dict，可以缓存中间计算结果（例如，在计算factorial(10)之后计算factorial(9)时，我们可以重用所有中间结果）

def factorial(n, _cache={1:1}):    
    try:            
        return _cache[n]           
    except IndexError:
        _cache[n] = factorial(n-1)*n
        return _cache[n]

- yegle

Answer 10

这里有一个适用于列表或字典类型参数的解决方案，可以正常工作而不会抱怨：

def memoize(fn):
    """returns a memoized version of any function that can be called
    with the same list of arguments.
    Usage: foo = memoize(foo)"""

    def handle_item(x):
        if isinstance(x, dict):
            return make_tuple(sorted(x.items()))
        elif hasattr(x, '__iter__'):
            return make_tuple(x)
        else:
            return x

    def make_tuple(L):
        return tuple(handle_item(x) for x in L)

    def foo(*args, **kwargs):
        items_cache = make_tuple(sorted(kwargs.items()))
        args_cache = make_tuple(args)
        if (args_cache, items_cache) not in foo.past_calls:
            foo.past_calls[(args_cache, items_cache)] = fn(*args,**kwargs)
        return foo.past_calls[(args_cache, items_cache)]
    foo.past_calls = {}
    foo.__name__ = 'memoized_' + fn.__name__
    return foo

请注意，通过在handle_item中实现自己的哈希函数作为特殊情况，可以将此方法自然地扩展到任何对象。例如，要使此方法适用于以集合作为输入参数的函数，您可以添加以下内容到handle_item:

if is_instance(x, set):
    return make_tuple(sorted(list(x)))

- RussellStewart

---

不错的尝试。不要抱怨，一个包含[1,2,3]的列表参数可能会被错误地认为与一个包含{1,2,3}值的不同集合参数相同。此外，集合与字典一样是无序的，因此它们也需要进行sorted()排序。还要注意，递归数据结构参数会导致无限循环。 - martineau

是的，集合应该通过特殊情况处理handle_item(x)和排序来处理。我不应该说这个实现处理集合，因为它并没有 - 但重点是它可以通过特殊情况处理handle_item轻松扩展到处理集合，并且对于任何类或可迭代对象都适用，只要你愿意自己编写哈希函数。棘手的部分 - 处理多维列表或字典 - 已经在这里处理了，所以我发现这个记忆化函数作为基础比简单的“我只接受可哈希参数”类型更容易使用。 - RussellStewart

我提到的问题是由于list和set被“元组化”成相同的东西，因此它们变得无法区分。你最新更新中描述添加对set支持的示例代码恐怕并没有避免这个问题。这可以通过将[1,2,3]和{1,2,3}分别作为参数传递给“memoize”测试函数，并观察它是否被调用两次来轻松验证。 - martineau

是的，我看到了那个问题，但我没有解决它，因为我认为它比你提到的另一个问题要小得多。你上次写记忆化函数是什么时候？其中一个固定参数可以是列表或集合，而这两个参数会产生不同的输出结果？如果你再次遇到这种罕见情况，你只需重新编写handle_item函数，在元素是集合时添加0，在元素是列表时添加1即可。 - RussellStewart

实际上，list和dict也存在类似的问题，因为一个list可能恰好包含与调用make_tuple(sorted(x.items()))生成的字典相同的内容。对于这两种情况的一个简单解决方案是在生成的元组中包括值的type()。我可以想到一种更简单的方法来处理set，但它并不具有普适性。 - martineau