Memoization

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();
            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.

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.