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