问题:什么是备忘录,如何在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的装饰图书馆有一个名为类似的装饰是不是稍微更强大的是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 that is slightly more robust than the Memoize
class shown here.
回答 1
是Python 3.2的新功能。默认情况下,它仅缓存最近使用的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
注释可确保如果最近已为特定值调用了该函数,则该函数不会重新计算该值,而是使用缓存的先前结果。在这种情况下,它可以极大地提高速度,而代码不会因缓存的细节而混乱。
New to Python 3.2 is . 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
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
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
.
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。