Welcome, guest | Sign In | My Account | Store | Cart
NOTE: Recipes have moved! Please visit GitHub.com/activestate/code for the current versions.

Memoize, but clear cache when last function call returns. Suitable for dynamic programming.

Python, 37 lines
 1
 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.

Created by Connelly Barnes on Sat, 8 Oct 2005 (PSF)
Python recipes (4591)
Connelly Barnes's recipes (7)

Required Modules

Other Information and Tasks