Tibor's Musings

Python Memoisation

If the profiling shows that you call some function a lot of times for the same arguments, then memoise it. The canonical example is memoising the intermediate results of the Fibonacci recursive calculator, presented below. But beware: if you do memoise, better make sure that you don't eat up the full memory! Memoising is a classic speed versus memory dilemma.

Here is example code, showing how memoisation speeded up Fibonacci calculator from 1.64 to 0.01 seconds:


Demonstrate the memoization technique for the Fibonacci calculator.

Results run on PCDH23 on 2004-12-06 are:

  $ python memoize-demo.py
  testing memoization for fib(20)...
  fib took 1.640 sec
  fib_memoized took 0.010 sec
  fib_memoized stats: calls in cache: 117 out of 138 (84.8%)


class Memoize:
    """Memoizator.  Based on <http://www.norvig.com/python-iaq.html>."""
    def __init__(self, function):
        self.memo = {}
        self.function = function
        self.count_calls_total = 0
        self.count_calls_in_cache = 0
    def __call__(self, *args):
        self.count_calls_total += 1
        if self.memo.has_key(args):
            self.count_calls_in_cache += 1
            return self.memo[args]
            object = self.memo[args] = self.function(*args)
            return object
    def get_stats(self):
        return "calls in cache: %d out of %d (%.1f%%)" % \

def fib(n):
    """Calculate Fibonacci number for N recursively."""
    if n < 2:
        return 1
        return fib(n-1) + fib(n-2)

def fib_memoized(n):
    """Calculate Fibonacci number for N recursively.
       Identical to fib() defined above.  This one will be memoized later.
    if n < 2:
        return 1
        return fib_memoized(n-1) + fib_memoized(n-2)

# memoize one of the two identical fib() functions
fib_memoized = Memoize(fib_memoized)

import time
def timing(f, a, n=10):
    """Return timing of function F on argument A run N times.
       Taken from <http://www.python.org/doc/essays/list2str.html>.
    r = range(n)
    t1 = time.clock()
    for i in r:
        f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a)
    t2 = time.clock()
    return round(t2-t1, 3)

def main():
    """Demonstrate the memoization technique for the Fibonacci calculator."""
    n = 20
    print "testing memoization for fib(%d)..." % n
    fib_time = timing(fib, n)
    fib_memoized_time = timing(fib_memoized, n)
    print "fib took %.3f sec" % fib_time
    print "fib_memoized took %.3f sec" % fib_memoized_time
    print "fib_memoized stats: %s" % fib_memoized.get_stats()

if __name__ == '__main__':