I have spent all night whipping up this recipe. It's my first Python decorator. I feel like I have a full understanding of how decorators work now and I think I came up with a good object-oriented algorithm to automatically provide memoization. Please let me know what you think.
I made a few quick changes after pasting it in here so please let me know if my changes broke something (don't have an interpreter on hand).
"""This provides a way of automatically memoizing a function. Using this eliminates the need for extra code. Below is an example of how it would be used on a recursive Fibonacci sequence function:
def fib(n):
if n in (0, 1): return n
return fib(n - 1) + fib(n - 2)
fib = memoize(fib)
That's all there is to it. That is nearly identical to the following:
_memos = {}
def fib(n):
if n in _memos:
return _memos[n]
if n in (0, 1):
_memos[n] = n
return _memos[n]
_memos[n] = fib(n - 1) + fib(n - 2)
return _memos[n]
The above is much more difficult to read than the first method. To make things even simpler, one can use the memoize function as a decorator like so:
@memoize
def fib(n):
if n in (0, 1): return n
return fib(n - 1) + fib(n - 2)
Both the first and third solutions are completely identical. However, the latter is recommended due to its elegance. Also, note that functions using keywords will purposely not work. This is because this memoization algorithm does not store keywords with the memos as it HEAVILY increases the CPU load. If you still want this functionality, please implement it at your own risk."""
class memoize:
"""Gives the class it's core functionality."""
def __call__(self, *args):
if args not in self._memos:
self._memos[args] = self._function(*args)
return self._memos[args]
def __init__(self, function):
self._memos = {}
self._function = function
# Please don't ask me to implement a get_memo(*args) function.
"""Indicated the existence of a particular memo given specific arguments."""
def has_memo(self, *args):
return args in self._memos
"""Returns a dictionary of all the memos."""
@property
def memos(self):
return self._memos.copy()
"""Remove a particular memo given specific arguments. This is particularly useful if the particular memo is no longer correct."""
def remove_memo(self, *args):
del self._memos[args]
"""Removes all memos. This is particularly useful if something that affects the output has changed."""
def remove_memos(self):
self._memos.clear()
"""Set a particular memo. This is particularly useful to eliminate double-checking of base cases. Beware, think twice before using this."""
def set_memo(self, args, value):
self._memos[args] = value
"""Set multiple memos. This is particular useful to eliminate double-checking of base cases. Beware, think twice before using this."""
def set_memos(self, map_of_memos):
self._memos.update(map_of_memos)
__call__
and__init__
? \$\endgroup\$ – Quentin Pradet Feb 29 '12 at 9:55set_memo(self, args, value)
andset_memos(self, map_of_memos)
? Eliminating particular base cases will usually not make too big of a difference. Also, something that the function uses may update and one may want to remove some or all values to recalculate them. I can't think of examples where one would want to do this, but I thought I'd throw it in there for the heck of it. \$\endgroup\$ – Tyler Crompton Feb 29 '12 at 17:12__contains__
instead ofhas_memo
? Then you can ask10 in fib
. \$\endgroup\$ – Adrian Panasiuk Mar 4 '12 at 2:02