Thursday, May 29, 2014

Function Caching via Memoization

To explain memoization, see these different versions of Fibonacci:

Purely recursive. Highly inefficient. Recalculates every value for every calculation.

Iterative. Much faster.

Here is the memoization technique. A 'cache' dictionary of { (args) : (return_val), } is created. This allows us to quickly locate and reuse any value that has already been calculated.

Here is the same memoization design, implemented as a decorator.

No comments:

Post a Comment