Python memoization decorator
Memoization, if you aren't already familiar with it, is a way to cache results of function calls to avoid repeating work.
from functools import wraps
def memoize(f):
"""A hacky memoize method decorator."""
def _c(*args, **kwargs):
if not hasattr(f, 'cache'):
f.cache = dict()
key = (args, tuple(kwargs))
if key not in f.cache:
f.cache[key] = f(*args, **kwargs)
return f.cache[key]
return wraps(f)(_c)For example, computing the Fibonacci sequence in the naive recursive way results in a ton of repeated computations.
def fib(x):
if x <= 0:
return 0
if x == 1:
return 1
return fib(x - 1) + fib(x - 2)fib(35) takes about 10 seconds to run on my machine. The recursive Fibonacci sequence scales at O(2^N) (though this is an upper bound).
If we use memoization, this is reduced to about a millisecond, and we can quickly compute much larger values.
@memoize
def fib(x):
if x <= 0:
return 0
if x == 1:
return 1
return fib(x - 1) + fib(x - 2)
>>> fib(100)
354224848179261915075LWritten by Steven
Related protips
Have a fresh tip? Share with Coderwall community!
Post
Post a tip
Best
#Cache
Authors
Sponsored by #native_company# — Learn More
#native_title#
#native_desc#