Memoization Decorator

Recently I had the opportunity to give a short 10 min presentation on Memoization Decorator at our local UtahPython Users Group meeting. 

Memoization: 

  • Everytime a function is called, save the results in a cache (map).
  • Next time the function is called with the exact same args, return the value from the cache instead of running the function.

The code for memoization decorator for python is here: http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

Example:

The typical recursive implementation of fibonacci calculation is pretty inefficient O(2^n).   

def fibonacci(num):
        print 'fibonacci(%d)'%num
        if num in (0,1):
            return num
        return fibonacci(num-1) + fibonacci(num-2)
>>> math_funcs.fibonacci(4)   # 9 function calls
    fibonacci(4)
    fibonacci(3)
    fibonacci(2)
    fibonacci(1)
    fibonacci(0)
    fibonacci(1)
    fibonacci(2)
    fibonacci(1)
    fibonacci(0)
    3

But the memoized version makes it ridiculously efficient O(n) with very little effort.

import memoized
@memoized
def fibonacci(num):
    print 'fibonacci(%d)'%num
    if num in (0,1):
        return num
    return fibonacci(num-1) + fibonacci(num-2)
    
>>> math_funcs.mfibonacci(4)  # 5 function calls
    fibonacci(4)
    fibonacci(3)
    fibonacci(2)
    fibonacci(1)
    fibonacci(0)
    3

We just converted an algorithm from Exponential Complexity to Linear Complexity by simply adding the memoization decorator.

Slides:

Presentation:

I generated the slides using LaTeX Beamer. But instead of writing raw LaTeX code I used reStructured Text (rst) and used rst2beamer script to generate the .tex file. 

Source:

The rst file and tex files are available in Github.

https://github.com/amjith/User-Group-Presentations/tree/master/memoization_de...