Welcome, guest | Sign In | My Account | Store | Cart
1

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.

Add a comment

Sign in to comment