Memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously-processed inputs. Memoization is also used in Dynamic Programming.

Memoization typically requires maintaining a look up table where calculated values of previous function calls are kept.

Naive examples where memoizaton can help is:

1. Factorial

2. Fibonacci Series

I will take up a small problem to show the technique:

Lets say we have to calculate value of a function A which is defined by:

An = A[n/p] + A[n/q] for all n >= 1, where [x] denotes the floor function of x.

for a given value of n.

A naive implementation looks like this:

using System;

using System.Collections.Generic;

using System.Text;

using System.Diagnostics;

namespace TC1 {

class Program {

Dictionarymem =new Dictionary () ;

long calc1 (long n, int p, int q) {

if (n == 0)

return 1;

long np = (long) Math.Floor((double)n / p);

long nq = (long) Math.Floor((double) n / q);

return calc1(np ,p , q) + calc1(nq, p ,q);

}

long calc2 (long n, int p, int q) {

if (n == 0)

return 1;

long val;

if (mem.TryGetValue(n, out val)) {

} else {

long np = (long) Math.Floor((double) n / p);

long nq = (long) Math.Floor((double) n / q);

val = calc2(np, p, q) + calc2(nq, p, q);

mem.Add(n, val);

}

return val;

}

static void Main(string [] args) {

Program p = new Program();

Stopwatch w = new Stopwatch();

w.Start();

Console.WriteLine(p.calc1(10000000, 2, 3));

w.Stop();

Console.WriteLine(w.Elapsed);

w.Reset();

w.Start();

Console.WriteLine(p.calc2(10000000, 2, 3));

w.Stop();

Console.WriteLine(w.Elapsed);

}

}

}

First of all, this is not the best way to benchmark techniques, but it does give a good general indication. As the value of n increases the memoization techniques is faster by more that a factor of 10 in many cases.

However, in some cases you have to tread carefully when there is a space constraint too. In most cases, the problem can be solved by using a threshold above which no memoization is done.