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

问题描述：

我刚开始学习 Python，不知道什么是memoization以及如何使用它。另外，可以给我一个简化的示例吗？

解决方案 1：

记忆化实际上是指根据方法输入记住（“记忆化”→“备忘录”→要记住）方法调用的结果，然后返回记住的结果，而不是再次计算结果。您可以将其视为方法结果的缓存。有关更多详细信息，请参阅Cormen 等人的《算法导论》 （3e）第 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这里显示的类稍微更强大一些。

解决方案 2：

functools.cache装饰者：

Python 3.9 发布了新功能functools.cache。它将使用一组特定参数调用的函数的结果缓存在内存中，这就是 memoization。它使用起来很简单：

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

解决方案 3：

其他答案已经很好地涵盖了这一点。我就不重复了。只是一些可能对你有用的要点。

通常，memoisation 是一种可以应用于任何计算某些东西（昂贵）并返回值的函数的操作。因此，它通常被实现为decorator。实现很简单，就像这样

memoised_function = memoise(actual_function)

或者表达为装饰器

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

解决方案 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)

解决方案 5：

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

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]

解决方案 6：

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

以下是一个例子：

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

更完整的描述可以在wikipedia 的 memoization 条目中找到。

解决方案 7：

记忆化基本上是保存使用递归算法完成的过去操作的结果，以便在以后需要进行相同计算时减少遍历递归树的需要。

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

Python 中的斐波那契记忆示例：

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]

解决方案 8：

记忆化是将函数转换为数据结构的过程。通常，人们希望转换以增量和惰性的方式进行（根据给定域元素或“键”的要求）。在惰性函数式语言中，这种惰性转换可以自动进行，因此可以在没有（显式）副作用的情况下实现记忆化。

解决方案 9：

好吧，我应该先回答第一部分：什么是记忆？

这只是用记忆换取时间的一种方法。想想乘法表。

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

这是一个改编自http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects的示例

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

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

解决方案 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)))

解决方案 11：

适用于位置参数和关键字参数的解决方案，与传递关键字参数的顺序无关（使用inspect.getargspec）：

import inspect
import functools

def memoize(fn):
    cache = fn.cache = {}
    @functools.wraps(fn)
    def memoizer(*args, **kwargs):
        kwargs.update(dict(zip(inspect.getargspec(fn).args, args)))
        key = tuple(kwargs.get(k, None) for k in inspect.getargspec(fn).args)
        if key not in cache:
            cache[key] = fn(**kwargs)
        return cache[key]
    return memoizer

类似问题：识别 Python 中用于记忆的等效 varargs 函数调用

解决方案 12：

只是想补充已经提供的答案，Python 装饰器库有一些简单但有用的实现，它们也可以记忆“不可散列类型”，不像functools.lru_cache。

解决方案 13：

cache = {}
def fib(n):
    if n <= 1:
        return n
    else:
        if n not in cache:
            cache[n] = fib(n-1) + fib(n-2)
        return cache[n]

解决方案 14：

如果考虑速度：

• @functools.cache并且@functools.lru_cache(maxsize=None)速度一样快，在我的系统上循环一百万次只需 0.122 秒（15 次运行中最好的一次）

• 全局缓存变量要慢得多，在我的系统上循环一百万次需要 0.180 秒（15 次运行中的最佳时间）

• 类self.cache变量的速度稍微慢了一点，在我的系统上循环一百万次需要 0.214 秒（15 次运行中最好的一次）

后两者的实现方式与目前得票最高的答案中描述的类似。

这没有内存耗尽预防功能，也就是说，我没有在class或global方法中添加代码来限制缓存的大小，这实际上是最基本的实现。lru_cache如果您需要，该方法可以免费提供此功能。

对我来说，一个悬而未决的问题是如何对带有functools装饰器的东西进行单元测试。是否有可能以某种方式清空缓存？单元测试似乎使用类方法（您可以为每个测试实例化一个新类）或其次使用全局变量方法（因为您可以yourimportedmodule.cachevariable = {}清空它）是最干净的。