标签归档:memoization

是否有一个装饰器来简单地缓存函数的返回值?

问题:是否有一个装饰器来简单地缓存函数的返回值?

考虑以下:

@property
def name(self):

    if not hasattr(self, '_name'):

        # expensive calculation
        self._name = 1 + 1

    return self._name

我是新手,但我认为可以将缓存分解为装饰器。只有我找不到喜欢的人;)

PS实际计算不取决于可变值

Consider the following:

@property
def name(self):

    if not hasattr(self, '_name'):

        # expensive calculation
        self._name = 1 + 1

    return self._name

I’m new, but I think the caching could be factored out into a decorator. Only I didn’t find one like it ;)

PS the real calculation doesn’t depend on mutable values


回答 0

从Python 3.2开始,有一个内置的装饰器:

@functools.lru_cache(maxsize=100, typed=False)

装饰器用备注可调用函数包装一个函数,该函数可保存最多最近调用的最大大小。当使用相同的参数定期调用昂贵的或I / O绑定的函数时,可以节省时间。

用于计算斐波纳契数的LRU缓存示例:

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

>>> print([fib(n) for n in range(16)])
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

>>> print(fib.cache_info())
CacheInfo(hits=28, misses=16, maxsize=None, currsize=16)

如果您对Python 2.x感到困惑,那么这里是其他兼容的备注库的列表:

Starting from Python 3.2 there is a built-in decorator:

@functools.lru_cache(maxsize=100, typed=False)

Decorator to wrap a function with a memoizing callable that saves up to the maxsize most recent calls. It can save time when an expensive or I/O bound function is periodically called with the same arguments.

Example of an LRU cache for computing Fibonacci numbers:

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

>>> print([fib(n) for n in range(16)])
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

>>> print(fib.cache_info())
CacheInfo(hits=28, misses=16, maxsize=None, currsize=16)

If you are stuck with Python 2.x, here’s a list of other compatible memoization libraries:


回答 1

听起来您好像并没有要求通用的备忘录装饰器(即,您对要为不同的参数值缓存返回值的一般情况不感兴趣)。也就是说,您想要这样:

x = obj.name  # expensive
y = obj.name  # cheap

而通用的备忘装饰器会为您提供:

x = obj.name()  # expensive
y = obj.name()  # cheap

我认为方法调用语法是更好的样式,因为它暗示了可能进行昂贵的计算,而属性语法则建议进行快速查找。

[更新:我以前链接并在此处引用的基于类的备忘录装饰器不适用于方法。我已经用装饰器函数代替了它。]如果您愿意使用通用的备忘录装饰器,这是一个简单的例子:

def memoize(function):
  memo = {}
  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)

这里可以找到另一个限制缓存大小的备忘装饰器。

It sounds like you’re not asking for a general-purpose memoization decorator (i.e., you’re not interested in the general case where you want to cache return values for different argument values). That is, you’d like to have this:

x = obj.name  # expensive
y = obj.name  # cheap

while a general-purpose memoization decorator would give you this:

x = obj.name()  # expensive
y = obj.name()  # cheap

I submit that the method-call syntax is better style, because it suggests the possibility of expensive computation while the property syntax suggests a quick lookup.

[Update: The class-based memoization decorator I had linked to and quoted here previously doesn’t work for methods. I’ve replaced it with a decorator function.] If you’re willing to use a general-purpose memoization decorator, here’s a simple one:

def memoize(function):
  memo = {}
  def wrapper(*args):
    if args in memo:
      return memo[args]
    else:
      rv = function(*args)
      memo[args] = rv
      return rv
  return wrapper

Example usage:

@memoize
def fibonacci(n):
  if n < 2: return n
  return fibonacci(n - 1) + fibonacci(n - 2)

Another memoization decorator with a limit on the cache size can be found here.


回答 2

class memorize(dict):
    def __init__(self, func):
        self.func = func

    def __call__(self, *args):
        return self[args]

    def __missing__(self, key):
        result = self[key] = self.func(*key)
        return result

样本用途:

>>> @memorize
... def foo(a, b):
...     return a * b
>>> foo(2, 4)
8
>>> foo
{(2, 4): 8}
>>> foo('hi', 3)
'hihihi'
>>> foo
{(2, 4): 8, ('hi', 3): 'hihihi'}
class memorize(dict):
    def __init__(self, func):
        self.func = func

    def __call__(self, *args):
        return self[args]

    def __missing__(self, key):
        result = self[key] = self.func(*key)
        return result

Sample uses:

>>> @memorize
... def foo(a, b):
...     return a * b
>>> foo(2, 4)
8
>>> foo
{(2, 4): 8}
>>> foo('hi', 3)
'hihihi'
>>> foo
{(2, 4): 8, ('hi', 3): 'hihihi'}

回答 3

Python 3.8 functools.cached_property装饰器

https://docs.python.org/dev/library/functools.html#functools.cached_property

cached_property在以下网址中提到了来自Werkzeug的文章:https : //stackoverflow.com/a/5295190/895245,但假设派生的版本将合并到3.8中,真是太棒了。

当没有任何参数时@property,可以将此装饰器视为缓存或清洁器 @functools.lru_cache

文档说:

@functools.cached_property(func)

将类的方法转换为属性,该属性的值将被计算一次,然后在实例生命周期中作为常规属性进行缓存。类似于property(),但增加了缓存。对于实例有效的不可变的昂贵的计算属性很有用。

例:

class DataSet:
    def __init__(self, sequence_of_numbers):
        self._data = sequence_of_numbers

    @cached_property
    def stdev(self):
        return statistics.stdev(self._data)

    @cached_property
    def variance(self):
        return statistics.variance(self._data)

3.8版的新功能。

注意此装饰器要求每个实例上的dict属性都是可变映射。这意味着它不适用于某些类型,例如元类(因为类型实例上的dict属性是类命名空间的只读代理),以及那些指定而不将dict作为已定义槽之一的类(例如此类)根本不提供dict属性)。

Python 3.8 functools.cached_property decorator

https://docs.python.org/dev/library/functools.html#functools.cached_property

cached_property from Werkzeug was mentioned at: https://stackoverflow.com/a/5295190/895245 but a supposedly derived version will be merged into 3.8, which is awesome.

This decorator can be seen as caching @property, or as a cleaner @functools.lru_cache for when you don’t have any arguments.

The docs say:

@functools.cached_property(func)

Transform a method of a class into a property whose value is computed once and then cached as a normal attribute for the life of the instance. Similar to property(), with the addition of caching. Useful for expensive computed properties of instances that are otherwise effectively immutable.

Example:

class DataSet:
    def __init__(self, sequence_of_numbers):
        self._data = sequence_of_numbers

    @cached_property
    def stdev(self):
        return statistics.stdev(self._data)

    @cached_property
    def variance(self):
        return statistics.variance(self._data)

New in version 3.8.

Note This decorator requires that the dict attribute on each instance be a mutable mapping. This means it will not work with some types, such as metaclasses (since the dict attributes on type instances are read-only proxies for the class namespace), and those that specify slots without including dict as one of the defined slots (as such classes don’t provide a dict attribute at all).


回答 4

Werkzeug有一个cached_property装饰器(docs源代码

Werkzeug has a cached_property decorator (docs, source)


回答 5

我编码了这个简单的装饰器类以缓存函数响应。我发现它对我的项目非常有用:

from datetime import datetime, timedelta 

class cached(object):
    def __init__(self, *args, **kwargs):
        self.cached_function_responses = {}
        self.default_max_age = kwargs.get("default_cache_max_age", timedelta(seconds=0))

    def __call__(self, func):
        def inner(*args, **kwargs):
            max_age = kwargs.get('max_age', self.default_max_age)
            if not max_age or func not in self.cached_function_responses or (datetime.now() - self.cached_function_responses[func]['fetch_time'] > max_age):
                if 'max_age' in kwargs: del kwargs['max_age']
                res = func(*args, **kwargs)
                self.cached_function_responses[func] = {'data': res, 'fetch_time': datetime.now()}
            return self.cached_function_responses[func]['data']
        return inner

用法很简单:

import time

@cached
def myfunc(a):
    print "in func"
    return (a, datetime.now())

@cached(default_max_age = timedelta(seconds=6))
def cacheable_test(a):
    print "in cacheable test: "
    return (a, datetime.now())


print cacheable_test(1,max_age=timedelta(seconds=5))
print cacheable_test(2,max_age=timedelta(seconds=5))
time.sleep(7)
print cacheable_test(3,max_age=timedelta(seconds=5))

I coded this simple decorator class to cache function responses. I find it VERY useful for my projects:

from datetime import datetime, timedelta 

class cached(object):
    def __init__(self, *args, **kwargs):
        self.cached_function_responses = {}
        self.default_max_age = kwargs.get("default_cache_max_age", timedelta(seconds=0))

    def __call__(self, func):
        def inner(*args, **kwargs):
            max_age = kwargs.get('max_age', self.default_max_age)
            if not max_age or func not in self.cached_function_responses or (datetime.now() - self.cached_function_responses[func]['fetch_time'] > max_age):
                if 'max_age' in kwargs: del kwargs['max_age']
                res = func(*args, **kwargs)
                self.cached_function_responses[func] = {'data': res, 'fetch_time': datetime.now()}
            return self.cached_function_responses[func]['data']
        return inner

The usage is straightforward:

import time

@cached
def myfunc(a):
    print "in func"
    return (a, datetime.now())

@cached(default_max_age = timedelta(seconds=6))
def cacheable_test(a):
    print "in cacheable test: "
    return (a, datetime.now())


print cacheable_test(1,max_age=timedelta(seconds=5))
print cacheable_test(2,max_age=timedelta(seconds=5))
time.sleep(7)
print cacheable_test(3,max_age=timedelta(seconds=5))

回答 6

免责声明:我是kids.cache的作者。

您应该检查kids.cache,它提供了@cache可在python 2和python 3上使用的装饰器。没有依赖项,大约100行代码。例如,考虑到您的代码,使用起来非常简单,您可以像这样使用它:

pip install kids.cache

然后

from kids.cache import cache
...
class MyClass(object):
    ...
    @cache            # <-- That's all you need to do
    @property
    def name(self):
        return 1 + 1  # supposedly expensive calculation

或者,您可以将@cache装饰器放在@property(相同结果)之后。

在属性上使用缓存称为惰性评估kids.cache可以做更多的事情(它可以在具有任何参数,属性,任何类型的方法,甚至是类的函数上工作)。对于高级用户,kids.cache支持cachetools可为python 2和python 3提供高级缓存存储(LRU,LFU,TTL,RR缓存)。

重要说明:的默认缓存存储区kids.cache是标准字典,不建议对运行时间长且查询内容不同的长期运行的程序进行存储,因为它会导致缓存存储区的不断增长。对于这种用法,您可以使用例如插入其他缓存存储(@cache(use=cachetools.LRUCache(maxsize=2))以装饰您的功能/属性/类/方法…)

DISCLAIMER: I’m the author of kids.cache.

You should check kids.cache, it provides a @cache decorator that works on python 2 and python 3. No dependencies, ~100 lines of code. It’s very straightforward to use, for instance, with your code in mind, you could use it like this:

pip install kids.cache

Then

from kids.cache import cache
...
class MyClass(object):
    ...
    @cache            # <-- That's all you need to do
    @property
    def name(self):
        return 1 + 1  # supposedly expensive calculation

Or you could put the @cache decorator after the @property (same result).

Using cache on a property is called lazy evaluation, kids.cache can do much more (it works on function with any arguments, properties, any type of methods, and even classes…). For advanced users, kids.cache supports cachetools which provides fancy cache stores to python 2 and python 3 (LRU, LFU, TTL, RR cache).

IMPORTANT NOTE: the default cache store of kids.cache is a standard dict, which is not recommended for long running program with ever different queries as it would lead to an ever growing caching store. For this usage you can plugin other cache stores using for instance (@cache(use=cachetools.LRUCache(maxsize=2)) to decorate your function/property/class/method…)


回答 7

嗯,只需要为此找到正确的名称:“ 惰性属性评估 ”。

我也经常这样做。也许我会在代码中使用该配方。

Ah, just needed to find the right name for this: “Lazy property evaluation“.

I do this a lot too; maybe I’ll use that recipe in my code sometime.


回答 8

这里有fastcache,它是“ Python 3 functools.lru_cache的C实现。与标准库相比提供了10-30倍的加速”。

选择的答案相同,只是导入不同:

from fastcache import lru_cache
@lru_cache(maxsize=128, typed=False)
def f(a, b):
    pass

此外,它还安装在Anaconda中,与需要安装的 functools不同。

There is fastcache, which is “C implementation of Python 3 functools.lru_cache. Provides speedup of 10-30x over standard library.”

Same as chosen answer, just different import:

from fastcache import lru_cache
@lru_cache(maxsize=128, typed=False)
def f(a, b):
    pass

Also, it comes installed in Anaconda, unlike functools which needs to be installed.


回答 9

Python Wiki上还有一个备忘录装饰器的示例:

http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

该示例有点聪明,因为如果参数可变,它将不会缓存结果。(检查该代码,它非常简单和有趣!)

There is yet another example of a memoize decorator at Python Wiki:

http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

That example is a bit smart, because it won’t cache the results if the parameters are mutable. (check that code, it’s very simple and interesting!)


回答 10

如果您使用的是Django Framework,则它具有此类属性以缓存API使用的视图或响应,@cache_page(time)并且还可以有其他选项。

例:

@cache_page(60 * 15, cache="special_cache")
def my_view(request):
    ...

可以在此处找到更多详细信息。

If you are using Django Framework, it has such a property to cache a view or response of API’s using @cache_page(time) and there can be other options as well.

Example:

@cache_page(60 * 15, cache="special_cache")
def my_view(request):
    ...

More details can be found here.


回答 11

备忘录示例一起,我找到了以下python软件包:

  • 粗暴的 ; 它允许设置ttl和/或缓存函数的调用次数;另外,人们可以使用基于文件的加密缓存…
  • 缓存

Along with the Memoize Example I found the following python packages:

  • cachepy; It allows to set up ttl and\or the number of calls for cached functions; Also, one can use encrypted file-based cache…
  • percache

回答 12

我实现了类似的方法,使用pickle进行持久化,并使用sha1来实现几乎确定的短唯一ID。基本上,缓存会对函数的代码和参数的历史进行哈希处理,以获取sha1,然后查找名称中具有sha1的文件。如果存在,则将其打开并返回结果。如果不是,它将调用该函数并保存结果(可选地,仅在处理了一定时间后才保存)。

就是说,我发誓我已经找到了一个执行此操作的现有模块,并发现自己在这里试图找到该模块…我能找到的最接近的是这个,看起来很正确:http://chase-seibert.github。 io / blog / 2011/11/23 / pythondjango-disk-based-caching-decorator.html

我唯一看到的问题是,它不能对大型输入有效,因为它会散列str(arg),这对于巨型数组并不是唯一的。

如果有一个unique_hash()协议让一个类返回其内容的安全哈希值,那就太好了。我基本上手动实现了我所关心的类型。

I implemented something like this, using pickle for persistance and using sha1 for short almost-certainly-unique IDs. Basically the cache hashed the code of the function and the hist of arguments to get a sha1 then looked for a file with that sha1 in the name. If it existed, it opened it and returned the result; if not, it calls the function and saves the result (optionally only saving if it took a certain amount of time to process).

That said, I’d swear I found an existing module that did this and find myself here trying to find that module… The closest I can find is this, which looks about right: http://chase-seibert.github.io/blog/2011/11/23/pythondjango-disk-based-caching-decorator.html

The only problem I see with that is it wouldn’t work well for large inputs since it hashes str(arg), which isn’t unique for giant arrays.

It would be nice if there were a unique_hash() protocol that had a class return a secure hash of its contents. I basically manually implemented that for the types I cared about.


回答 13

尝试joblib http://pythonhosted.org/joblib/memory.html

from joblib import Memory
memory = Memory(cachedir=cachedir, verbose=0)
@memory.cache
    def f(x):
        print('Running f(%s)' % x)
        return x

Try joblib http://pythonhosted.org/joblib/memory.html

from joblib import Memory
memory = Memory(cachedir=cachedir, verbose=0)
@memory.cache
    def f(x):
        print('Running f(%s)' % x)
        return x

回答 14

如果您使用的是Django,并且想缓存视图,请参见Nikhil Kumar的答案


但是,如果要缓存ANY函数结果,则可以使用django-cache-utils

它重用了Django缓存并提供了易于使用的cached装饰器:

from cache_utils.decorators import cached

@cached(60)
def foo(x, y=0):
    print 'foo is called'
    return x+y

If you are using Django and want to cache views, see Nikhil Kumar’s answer.


But if you want to cache ANY function results, you can use django-cache-utils.

It reuses Django caches and provides easy to use cached decorator:

from cache_utils.decorators import cached

@cached(60)
def foo(x, y=0):
    print 'foo is called'
    return x+y

回答 15

@lru_cache 不适合使用默认功能值

我的mem装饰:

import inspect


def get_default_args(f):
    signature = inspect.signature(f)
    return {
        k: v.default
        for k, v in signature.parameters.items()
        if v.default is not inspect.Parameter.empty
    }


def full_kwargs(f, kwargs):
    res = dict(get_default_args(f))
    res.update(kwargs)
    return res


def mem(func):
    cache = dict()

    def wrapper(*args, **kwargs):
        kwargs = full_kwargs(func, kwargs)
        key = list(args)
        key.extend(kwargs.values())
        key = hash(tuple(key))
        if key in cache:
            return cache[key]
        else:
            res = func(*args, **kwargs)
            cache[key] = res
            return res
    return wrapper

和测试代码:

from time import sleep


@mem
def count(a, *x, z=10):
    sleep(2)
    x = list(x)
    x.append(z)
    x.append(a)
    return sum(x)


def main():
    print(count(1,2,3,4,5))
    print(count(1,2,3,4,5))
    print(count(1,2,3,4,5, z=6))
    print(count(1,2,3,4,5, z=6))
    print(count(1))
    print(count(1, z=10))


if __name__ == '__main__':
    main()

结果-睡眠只有3次

但这@lru_cache将是4次,因为:

print(count(1))
print(count(1, z=10))

将被计算两次(默认情况下无效)

@lru_cache is not perfect with default function values

my mem decorator:

import inspect


def get_default_args(f):
    signature = inspect.signature(f)
    return {
        k: v.default
        for k, v in signature.parameters.items()
        if v.default is not inspect.Parameter.empty
    }


def full_kwargs(f, kwargs):
    res = dict(get_default_args(f))
    res.update(kwargs)
    return res


def mem(func):
    cache = dict()

    def wrapper(*args, **kwargs):
        kwargs = full_kwargs(func, kwargs)
        key = list(args)
        key.extend(kwargs.values())
        key = hash(tuple(key))
        if key in cache:
            return cache[key]
        else:
            res = func(*args, **kwargs)
            cache[key] = res
            return res
    return wrapper

and code for testing:

from time import sleep


@mem
def count(a, *x, z=10):
    sleep(2)
    x = list(x)
    x.append(z)
    x.append(a)
    return sum(x)


def main():
    print(count(1,2,3,4,5))
    print(count(1,2,3,4,5))
    print(count(1,2,3,4,5, z=6))
    print(count(1,2,3,4,5, z=6))
    print(count(1))
    print(count(1, z=10))


if __name__ == '__main__':
    main()

result – only 3 times with sleep

but with @lru_cache it will be 4 times, because this:

print(count(1))
print(count(1, z=10))

will be calculated twice (bad working with defaults)


什么是备忘录,如何在Python中使用备忘录?

问题:什么是备忘录,如何在Python中使用备忘录?

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

I just started Python and I’ve got no idea what memoization is and how to use it. Also, may I have a simplified example?


回答 0

记忆有效地指基于方法输入记忆方法调用的结果(“记忆”→“备忘录”→要记忆),然后返回记忆的结果,而不是再次计算结果。您可以将其视为方法结果的缓存。有关更多详细信息,请参见第387页,Cormen等人的算法简介(3e)中的定义。

一个简单的示例,使用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这里显示类。

Memoization effectively refers to remembering (“memoization” → “memorandum” → to be remembered) results of method calls based on the method inputs and then returning the remembered result rather than computing the result again. You can think of it as a cache for method results. For further details, see page 387 for the definition in Introduction To Algorithms (3e), Cormen et al.

A simple example for computing factorials using memoization in Python would be something like this:

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]

You can get more complicated and encapsulate the memoization process into a class:

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]

Then:

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

factorial = Memoize(factorial)

A feature known as “decorators” was added in Python 2.4 which allow you to now simply write the following to accomplish the same thing:

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

The Python Decorator Library has a similar decorator called memoized that is slightly more robust than the Memoize class shown here.


回答 1

是Python 3.2的新功能functools.lru_cache。默认情况下,它仅缓存最近使用的128个调用,但是您可以将设置为maxsizeNone以指示缓存永不过期:

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

New to Python 3.2 is functools.lru_cache. By default, it only caches the 128 most recently used calls, but you can set the maxsize to None to indicate that the cache should never expire:

import functools

@functools.lru_cache(maxsize=None)
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

This function by itself is very slow, try fib(36) and you will have to wait about ten seconds.

Adding lru_cache annotation ensures that if the function has been called recently for a particular value, it will not recompute that value, but use a cached previous result. In this case, it leads to a tremendous speed improvement, while the code is not cluttered with the details of caching.


回答 2

其他答案涵盖了它相当不错的地方。我不再重复。只是一些对您可能有用的观点。

通常,备注是一项操作,您可以将其应用于可计算某些内容(昂贵)并返回值的任何函数。因此,通常将其实现为装饰器。实现很简单,就像这样

memoised_function = memoise(actual_function)

或表示为装饰者

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

The other answers cover what it is quite well. I’m not repeating that. Just some points that might be useful to you.

Usually, memoisation is an operation you can apply on any function that computes something (expensive) and returns a value. Because of this, it’s often implemented as a decorator. The implementation is straightforward and it would be something like this

memoised_function = memoise(actual_function)

or expressed as a decorator

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

回答 3

备注保持了昂贵的计算结果并返回缓存的结果,而不是不断地重新计算它。

这是一个例子:

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

有关备注的详细信息,请参见Wikipedia条目

Memoization is keeping the results of expensive calculations and returning the cached result rather than continuously recalculating it.

Here’s an example:

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

A more complete description can be found in the wikipedia entry on memoization.


回答 4

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]

Let’s not forget the built-in hasattr function, for those who want to hand-craft. That way you can keep the mem cache inside the function definition (as opposed to a global).

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]

回答 5

我发现这非常有用

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)

I’ve found this extremely useful

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)

回答 6

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

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

Memoization is basically saving the results of past operations done with recursive algorithms in order to reduce the need to traverse the recursion tree if the same calculation is required at a later stage.

see http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/

Fibonacci Memoization example in 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]

回答 7

记忆化是将功能转换为数据结构。通常,人们希望转换是渐进地和惰性地进行(根据给定的域元素或“键”的需求)。在惰性函数语言中,这种惰性转换可以自动发生,因此可以实现备忘录而没有(显式)副作用。

Memoization is the conversion of functions into data structures. Usually one wants the conversion to occur incrementally and lazily (on demand of a given domain element–or “key”). In lazy functional languages, this lazy conversion can happen automatically, and thus memoization can be implemented without (explicit) side-effects.


回答 8

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

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

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

Well I should answer the first part first: what’s memoization?

It’s just a method to trade memory for time. Think of Multiplication Table.

Using mutable object as default value in Python is usually considered bad. But if use it wisely, it can actually be useful to implement a memoization.

Here’s an example adapted from http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects

Using a mutable dict in the function definition, the intermediate computed results can be cached (e.g. when calculating factorial(10) after calculate factorial(9), we can reuse all the intermediate results)

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

回答 9

这是一个可以使用列表或字典类型参数而无需抱怨的解决方案:

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

Here is a solution that will work with list or dict type arguments without whining:

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

Note that this approach can be naturally extended to any object by implementing your own hash function as a special case in handle_item. For example, to make this approach work for a function that takes a set as an input argument, you could add to handle_item:

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

回答 10

与位置参数和关键字参数一起使用的解决方案,与关键字args的传递顺序无关(使用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

相似的问题:确定等效的varargs函数调用以在Python中进行记忆

Solution that works with both positional and keyword arguments independently of order in which keyword args were passed (using 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

Similar question: Identifying equivalent varargs function calls for memoization in Python


回答 11

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

回答 12

只是想添加到已经提供的答案中,Python装饰器库具有一些简单但有用的实现,与相比,它们还可以记住“无法散列的类型” functools.lru_cache

Just wanted to add to the answers already provided, the Python decorator library has some simple yet useful implementations that can also memoize “unhashable types”, unlike functools.lru_cache.