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

Question

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

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

Python 3.2的新功能是functools.lru_cache.默认情况下,它只缓存128个最近使用的来电,但你可以设置maxsize到None以表明缓存应当永不过期:

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注释可确保如果最近为特定值调用了函数,则不会重新计算该值,而是使用缓存的先前结果.在这种情况下,它会带来巨大的速度提升,而代码不会被缓存的细节混乱.

Answer 3

其他答案涵盖了很好的内容.我不是在重复.只是一些可能对您有用的要点.

通常,memoisation是一种可以应用于计算某些东西(昂贵)并返回值的任何函数的操作.因此,它通常被实现为装饰器.实现很简单,就像这样

memoised_function = memoise(actual_function)

或表达为装饰者

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

Answer 4

Memoization保持昂贵计算的结果并返回缓存结果而不是连续重新计算它.

这是一个例子:

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

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

Answer 5

让我们不要忘记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]

Answer 6

我发现这非常有用

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)

Answer 7

Memoization基本上保存了使用递归算法完成的过去操作的结果,以便在稍后阶段需要相同的计算时减少遍历递归树的需要.

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

Answer 8

Memoization是将函数转换为数据结构.通常,人们希望转换以递增和懒惰的方式发生(根据给定域元素的要求 - 或"密钥").在惰性函数语言中,这种惰性转换可以自动发生,因此可以在没有(显式)副作用的情况下实现memoization.

Answer 9

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

这只是以时间交换内存的一种方法。想一想乘法表。

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

这是一个改编自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]