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...