Python Cookbook

Memoizing (Caching) the Return Values of Functions

Credit: Paul Moore

Problem

You have a pure function that is often called with the same arguments (particularly a recursive function) and is slow to compute its results, and you are looking for a simple way to gain substantial performance.

Solution

The key idea behind memoizing is to store a function’s results in a dictionary, keyed by the arguments that produce each result. Of course, this makes sense only for a pure function (i.e., one that yields the same result when called repeatedly with given arguments). It’s easy to memoize a function by hand. For example, using the recursive Fibonacci function:

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]

Having to code the memoization inside each function to be memoized, however, is repetitive and interferes with the function’s readability. A good alternative is to encapsulate the memoization mechanics into a class:

class Memoize:
    def _ _init_ _(self, fn):
        self.fn = fn
        self.memo = {}
        self.cacheable = self.misses = self.noncacheable = 0L
    def _ _call_ _(self, *args, **kwds):
        if not kwds:
            self.cacheable += 1
            try: return self.memo[args]
            except KeyError:
                self.misses += 1
                self.memo[args] = self.fn(*args)
                return self.memo[args]
            except TypeError: self.cacheable -= 1
        self.noncacheable += 1
        return self.fn(*args, **kwds)

Using this class to memoize fib, the function definition becomes obvious without caching boilerplate ...