什么是内存化，如何在Python中使用它?

记忆实际上是指根据方法输入记住(“记忆”→“备忘录”→被记住)方法调用的结果，然后返回记住的结果，而不是重新计算结果。您可以把它看作是方法结果的缓存。有关更多详细信息，请参阅第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中添加了一个名为“修饰符”的特性，它允许你现在简单地编写以下代码来完成相同的事情:

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

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

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

这里有一个例子:

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

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

其他答案很好地涵盖了它的本质。我不是在重复。只是一些可能对你有用的观点。

通常，memoisation是一种可以应用在任何函数上的操作，该函数计算一些东西(昂贵的)并返回一个值。因此，它通常被实现为装饰。实现很简单，大概是这样的

memoised_function = memoise(actual_function)

或者表示为装饰者

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

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

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

看到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]

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]

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

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

下面是一个解决方案，将工作与列表或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中实现您自己的哈希函数，这种方法可以自然地扩展到任何对象。例如，为了使这种方法适用于一个接受set作为输入参数的函数，你可以在handle_item中添加:

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

与传递关键字参数的顺序无关的位置参数和关键字参数的解决方案(使用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中识别用于内存化的等效可变参数函数调用

我应该先回答第一部分:什么是记忆?

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

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

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

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

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

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

我们不要忘记内置的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]

我发现这非常有用

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)

如果要考虑速度:

• @functools.cache和@functools.lru_cache(maxsize=None)同样快，在我的系统上循环一百万次需要0.122秒(最好运行15次)
• 全局缓存变量要慢得多，在我的系统上循环一百万次需要0.180秒(最好运行15次)
• self.cache类变量仍然有点慢，在我的系统上循环一百万次需要0.214秒(最好运行15次)

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

这没有防止内存耗尽，也就是说，我没有在class或global方法中添加代码来限制缓存的大小，这实际上是最基本的实现。lru_cache方法有免费的，如果你需要的话。

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