Monday, August 18, 2008


From wikipedia:
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 {
Dictionary mem =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();
Console.WriteLine(p.calc1(10000000, 2, 3));
Console.WriteLine(p.calc2(10000000, 2, 3));

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.

Saturday, August 2, 2008

First Post

This is the blog which I have started to keep track my efforts to become a better programmer. The focus of the blog would vary from learning new languages, algorithms, design patterns etc.
Related Posts with Thumbnails