Python Memoize Decorator¶
Section author: momo <mobeiheart@gmail.com>
A comparison between node.js and python, measures the time of running recursive fibonacci functions, the former is much faster than the latter, which may be the cause of v8 engine:
def memoize(f):
cache = {}
def decorated_function(*args):
if args in cache:
return cache[args]
else:
cache[args] = f(*args)
return cache[args]
return decorated_function
But you can use memoize in python to speed up, its function form sets up a closure cached the values have been computed.
On the other hand, it also can be implemented by class:
import collections
import functools
class memoized(object):
'''Decorator. Caches a function's return value each time it is called.
If called later with the same arguments, the cached value is returned
(not reevaluated).
'''
def __init__(self, func):
self.func = func
self.cache = {}
def __call__(self, *args):
if not isinstance(args, collections.Hashable):
# uncacheable. a list, for instance.
# better to not cache than blow up.
return self.func(*args)
if args in self.cache:
return self.cache[args]
else:
value = self.func(*args)
self.cache[args] = value
return value
def __repr__(self):
'''Return the function's docstring.'''
return self.func.__doc__
def __get__(self, obj, objtype):
'''Support instance methods.'''
return functools.partial(self.__call__, obj)
@memoized
def fibonacci(n):
"Return the nth fibonacci number."
if n in (0, 1):
return n
return fibonacci(n-1) + fibonacci(n-2)
print fibonacci(12)
The class has an instance variable of dict to store the values, the cache key must be hashable for using as an dict key, memoized_function([1, 2], [3, 4]) will not be cached:
class Fibonacci(object):
@memoized
def get_result(self, n):
if n in (0, 1):
return n
return self.get_result(n-1) + self.get_result(n-2)
# provided: memoized_get_result = memoized(get_result)
f = Fibonacci()
f.get_result(10)
The definition of __get__ lets f.get_result(*args) be equal to f.memoized_get_result.__call__(f.memoized_get_result, *args) and makes it possible to decorate instance methods.