什么是memoization，我怎样才能在Python中使用它？
我刚开始Python，我不知道什么是memoization ，以及如何使用它。 另外，我可以有一个简单的例子吗？
记忆有效地指的是基于方法input记忆方法调用的结果（“记忆”→“备忘录”→记住），然后返回记忆的结果而不是再次计算结果。 您可以将其视为方法结果的caching。 有关更多详细信息，请参阅第387页， 以了解algorithm导论 （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) return self.memo[args]
然后：
def factorial(k): if k < 2: return 1 return k * factorial(k - 1) factorial = Memoize(factorial)
在Python 2.4中添加了一个名为“ 装饰器 ”的function，现在您可以简单地编写以下代码来完成相同的任务：
@Memoize def factorial(k): if k < 2: return 1 return k * factorial(k - 1)
Python装饰器库有一个类似的装饰器，称为memoized ，比这里显示的Memoize类Memoize 。
Python 3.2新增了functools.lru_cache 。 默认情况下，它只caching128个最近使用过的调用，但是可以将maxsize设置为None来指示caching不应该过期：
import functools @functools.lru_cache(maxsize=None) def fib(num): if num < 2: return num else: return fib(num-1) + fib(num-2)
这个函数本身是非常慢的，试试fib(36) ，你将不得不等待大约十秒。
添加lru_cache注释可以确保如果最近为特定的值调用函数，则不会重新计算该值，而是使用caching的以前的结果。 在这种情况下，会导致速度的巨大提升，而代码不会混淆caching的细节。
其他答案涵盖了什么是相当好的。 我不重复。 只是有些点可能对你有用。
通常，memoisation是一种操作，您可以将其应用于计算某些东西（昂贵）并返回值的任何函数。 正因为如此，它通常作为装饰器来实现。 实现很简单，就是这样的
memoised_function = memoise(actual_function)
或表示为装饰者
@memoise def actual_function(arg1, arg2): #body
记忆是保持昂贵的计算结果，并返回caching的结果，而不是不断重新计算。
这是一个例子：
def doSomeExpensiveCalculation(self, input): if input not in self.cache: <do expensive calculation> self.cache[input] = result return self.cache[input]
更多的完整描述可以在记忆中的维基百科条目中find。
让我们不要忘记内置hasattr函数，为那些谁想要手工。 这样你就可以将memcaching保存在函数定义中（而不是全局的）。
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]
我发现这非常有用
def memoize(function): from functools import wraps memo = {} @wraps(function) def wrapper(*args): if args in memo: return memo[args] else: rv = function(*args) memo[args] = rv return rv return wrapper @memoize def fibonacci(n): if n < 2: return n return fibonacci(n - 1) + fibonacci(n - 2) fibonacci(25)
Memoization基本上是保存了recursionalgorithm完成的过去操作的结果，以便在稍后阶段需要相同的计算时减less遍历recursion树的需要。
见http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/
Python中的Fibonacci Memoization示例：
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]
记忆是function到数据结构的转换。 通常情况下，人们希望转换发生在一个给定的域元素（或“键”）的增量和延迟的情况下。 在懒惰的函数式语言中，这种懒惰的转换可以自动发生，因此可以在没有（明确的）副作用的情况下实现记忆。
这是一个解决scheme，可以使用list或dicttypes的参数而不发牢骚：
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中实现自己的散列函数作为特殊情况，这种方法可以自然地扩展到任何对象。 例如，要使这种方法适用于以集合作为input参数的函数，可以添加到handle_item：
if is_instance(x, set): return make_tuple(sorted(list(x)))
那么我应该回答第一部分：什么是记忆？
这只是一种交易记忆的方法。 考虑乘法表 。
在Python中使用可变对象作为默认值通常被认为是不好的。 但是，如果明智地使用它，实施memoization实际上可能是有用的。
这是一个从http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects
在函数定义中使用可变dict ，中间计算结果可以被caching（例如，在计算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]
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]
与位置参数和关键字参数一起工作的解决scheme，与关键字参数的传递顺序无关（使用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函数调用memoization
只是想添加已经提供的答案， Python装饰器库有一些简单而有用的实现，也可以记忆“不可互换的types”，不像functools.lru_cache 。
