Memoize, but clear cache when last function call returns. Suitable for dynamic programming.
Python, 37 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | import cPickle
# Public domain.
def memoize(f):
"""
Memoize function, clear cache on last return.
"""
count = [0]
cache = {}
def g(*args, **kwargs):
count[0] += 1
try:
try:
if len(kwargs) != 0: raise ValueError
hash(args)
key = (args,)
except:
key = cPickle.dumps((args, kwargs))
if key not in cache:
cache[key] = f(*args, **kwargs)
return cache[key]
finally:
count[0] -= 1
if count[0] == 0:
cache.clear()
return g
# Example usage
def fib(n):
if n in [0, 1]: return n
return fib(n-1)+fib(n-2)
fib = memoize(fib)
print fib(300)
|
Memoization as presented in Recipe 52201 uses ever-increasing amounts of memory, since items are never evicted from the cache. In some use cases (e.g. dynamic programming), it is acceptable to clear the cache when the last function call returns. The memoize() function given in this recipe does that.
This recipe handles both mutable and immutable arguments.
Tags: algorithms
