Tuesday, May 8, 2012

What is memoization? Explanation with an example.

Memoization is the process of storing partially computed subproblems in a table to reduce the compute time of your problem.

We will explain the concept of memoization through a nice example from Wikipedia on fibonacci series:

Fibonacci sequence
Here is a na├»ve implementation of a function finding the nth member of the Fibonacci sequence, based directly on the mathematical definition:
   function fib(n)
       if n = 0 return 0
       if n = 1 return 1
       return fib(n − 1) + fib(n − 2)
Notice that if we call, say, fib(5), we produce a call tree that calls the function on the same value many different times:
  1. fib(5)
  2. fib(4) + fib(3)
  3. (fib(3) + fib(2)) + (fib(2) + fib(1))
  4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
  5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
In particular, fib(2) was calculated three times from scratch. In larger examples, many more values of fib, or subproblems, are recalculated, leading to an exponential time algorithm.
Now, suppose we have a simple map object, m, which maps each value of fib that has already been calculated to its result, and we modify our function to use it and update it. The resulting function requires only O(n) time instead of exponential time:
   var m := map(0 → 0, 1 → 1)
   function fib(n)
       if map m does not contain key n
           m[n] := fib(n − 1) + fib(n − 2)
       return m[n]
This technique of saving values that have already been calculated is called memoization; this is the top-down approach, since we first break the problem into subproblems and then calculate and store values.


Post a Comment