什么是备忘录,如何在Python中使用备忘录? [英] What is memoization and how can I use it in Python?
问题描述
我刚开始使用Python,不知道记忆化是什么以及如何使用它.另外,我可以举一个简化的例子吗?
记忆有效地指基于方法输入记住方法调用的结果(记忆"→备忘录"→要记忆),然后返回记忆的结果而不是再次计算结果.您可以将其视为方法结果的缓存.有关更多详细信息,请参阅第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装饰器库具有类似的装饰器,称为memoization is and how to use it. Also, may I have a simplified example?
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.
这篇关于什么是备忘录,如何在Python中使用备忘录?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!