Python

Memoizing

Last modified Feb. 26, 2009 | Revision 9

A simple python decorator that makes a function implement a Memoization Strategy: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class memoize(object):
    """memoize function decorator. converts a simple callable to be memoizable"""
    
    def __init__(self, callable):
        self._memo = {}        
        self._callable = callable

    def __call__(self, *args):        
        if args not in self._memo:        
            self._memo[args] = self._callable(*args)
        return self._memo[args]

@memoize
def fac(n):
    if n <= 1: 
        return 1
    return n * fac(n - 1)

@memoize
def fib(n):
    if n <= 1:
        return 1

    return fib(n - 1) + fib(n - 2)

Note, it requires all the arguments to be hashable - this rules of lists for example

Last modified Feb. 26, 2009 | Revision 9