python - 什么是 memoization 以及如何在 Python 中使用它？

Question

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

Answer 1

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

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

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]

您可以变得更复杂，并将 memoization 过程封装到一个类中：

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这里显示的类更健壮。

Answer 2

functools.cache装饰师：

Python 3.9 发布了一个新功能functools.cache。它将使用一组特定参数调用的函数的结果缓存在内存中，这就是记忆化。它易于使用：

import functools

@functools.cache
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

没有装饰器的这个函数很慢，尝试一下fib(36)，你将不得不等待大约十秒钟。

添加cache装饰器可确保如果最近针对特定值调用了该函数，它将不会重新计算该值，而是使用缓存的先前结果。在这种情况下，它会带来巨大的速度提升，同时代码不会因为缓存的细节而杂乱无章。

functools.lru_cache装饰师：

如果您需要支持旧版本的 Python，functools.lru_cache请使用 Python 3.2+。默认情况下，它只缓存最近使用的 128 个调用，但您可以将 设置maxsize为None以指示缓存永不过期：

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

---

Answer 3

其他答案涵盖了它的优点。我不再重复了。只是一些可能对你有用的点。

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

memoised_function = memoise(actual_function)

或表示为装饰者

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

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)

Answer 5

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

这是一个例子：

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

更完整的描述可以在wikipedia entry on memoization中找到。

Answer 6

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]

Answer 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]

Answer 8

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

Answer 9

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

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

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

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

在函数定义中使用 mutable 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]

Answer 10

这是一个可以使用 list 或 dict 类型参数而不会抱怨的解决方案：

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

Answer 11

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

Answer 12

使用位置和关键字参数的解决方案与传递关键字参数的顺序无关（使用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 中识别等效的可变参数函数调用以进行记忆

Answer 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]