Memoization

From Algorithmist
Jump to: navigation, search

Memoization is a technique that is associated with Dynamic Programming. The concept is to cache the result of a function given its parameter so that the calculation will not be repeated; it is simply retrieved, or memo-ed. Most of the time a simple array is used for the cache table, but a hash table or map could also be employed.

[edit] Example

Consider a naive function that recursively calculates the Fibonacci Sequence:

function fib(n)
   if (n = 0)
      return 0
   if (n = 1)
      return 1
   return fib(n-1) + fib(n-2)

The above function runs in exponential time. Since fib(n) will never change, and the function produces no side-effects (such as printing to a file), we can memoize the results, giving linear time.

declare fib_table as array; all values initialized to 0

function fib_memo(n)
   if (n = 0)
      return 0
   if (n = 1)
      return 1

   if (fib_table[n] == 0)
     fib_table[n] = fib_memo(n-1) + fib_memo(n-2)

   return fib_table[n]

Be careful when choosing a default value for the memoization table. Zero is fine for this example, because the only time zero appears is for F0, which is accounted for explicitly. If your function's range is all integers, you may have to use an auxiliary table to keep track of whether a specific value has been computed.

Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox