Memoizing (cacheing) function return values « Python recipes « ActiveState Code (original) (raw)
For functions which are called often, particulary recursive functions or functions which are intensive to calculate, memoizing (cacheing) the return values can dramatically improve performance.
| 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | # Functions can be memoised "by hand" using a dictionary to hold # the return values when they are calculated: # Here is a simple case, using the recursive fibonnaci function # f(n) = f(n-1) + f(n-2) fib_memo = {} def fib(n): if n < 2: return 1 if not fib_memo.has_key(n): fib_memo[n] = fib(n-1) + fib(n-2) return fib_memo[n] # To encapsulate this in a class, use the Memoize class: class Memoize: """Memoize(fn) - an instance which acts like fn but memoizes its arguments Will only work on functions with non-mutable arguments """ def __init__(self, fn): self.fn = fn self.memo = {} def __call__(self, *args): if not self.memo.has_key(args): self.memo[args] = self.fn(*args) return self.memo[args] # And here is how to use this class to memoize fib(). Note that the definition # for fib() is now the "obvious" one, without the cacheing code obscuring # the algorithm. def fib(n): if n < 2: return 1 return fib(n-1) + fib(n-2) fib = Memoize(fib) # For functions taking mutable arguments, use the cPickle module, as # in class MemoizeMutable: class MemoizeMutable: """Memoize(fn) - an instance which acts like fn but memoizes its arguments Will work on functions with mutable arguments (slower than Memoize) """ def __init__(self, fn): self.fn = fn self.memo = {} def __call__(self, *args): import cPickle str = cPickle.dumps(args) if not self.memo.has_key(str): self.memo[str] = self.fn(*args) return self.memo[str] |
|---|
Note that when using the Memoize class, it is important that the value of fib is replaced by the memoized version. Storing the memoized version elsewhere, as in memoized_fib = Memoize(fib) will not work, because the recursive calls will call fib() directly, bypassing the cache.
Obviously, functions to be memoized must have no side effects, and return the same value whenever they are called with the same set of arguments.
More significantly, the Memoize class (and the inline version above) does not cater for functions which take mutable arguments, such as length() on a list. More precisely, the argument tuple must be suitable for use as a dictionary key. (Note that you can't memoize functions which change their mutable arguments, in any case). The MemoizeMutable class handles mutable arguments, by pickling the argument tuple into a constant string.