Code Optimization Technique: You Need Memoization!

Memoization is a pretty slick trick--a must know for those using interpreted languages and working with large datasets. My definition of memoization is basically when one uses a data structure to save the output of a function to memory using the inputs as a key. 


Imagine the case where recursive function must be used. Using memoization, the program won't need recalculate values in each recursion at run-time. Appropriate use can substantially speed up one's code.


Before Code:

$ cat fib.py
def fib(n):
        if n==1 or n==0:
                return 1
        return fib(n-2) + fib(n-1)


print fib(35)

Before Code (using 35 as the input value):
$ time python fib.py
14930352


real    0m5.718s
user    0m5.714s
sys     0m0.002s




After Code:

$ cat fib-memo.py
def memoize(f):
    cache= {}
    def memf(*x):
        if x not in cache:
            cache[x] = f(*x)
        return cache[x]
    return memf


@memoize #this is a decorator
def fib(n):
    if n==1 or n==0:
        return 1
    return fib(n-2) + fib(n-1)


#fib = memoize(fib) #an alternative to the decorator
print fib(300)

After Code (using 300 as the input value):
$ time python fib-memo.py
359579325206583560961765665172189099052367214309267232255589801


real    0m0.008s
user    0m0.004s
sys     0m0.004s

Python resources:

• IncPy - This software is an actual python interpreter written to automatically memoize code. It can be faster or slower than a normal python interpreter depending on what is being run.
• code.activestate.com