Memoization

I have been meaning to write short posts about interesting programming concepts and alternative programming movements (like alt.net). Topic of this post is an interesting programming concept called Memoization and its implementation in C# as a method attribute.

Memoization is an optimization technique which speeds up a program by remembering the values returned by function calls for specific input values, its also known as tabling.

Many of the new languages (Ruby, Python, C#) provide a very neat way to implement Memoization and many functional languages (Lisp, OCaml) have it as a first class construct for the runtime. Here is a my cheap implementation showing how one can use an integer based Memo attribute in C#

class Test
{   [Memo]
    public int DoSomething(int i)
    {
        for (int k = 0; k < 10000; k++)
        {
            int j = 0;
            j = j + 500;
        }
        Console.WriteLine("DoSomething " + i);
        return i + 5;
    }
}

Here is a simple driver which implements the Memoization :

static void Main(string[] args)
 {
     Debug.WriteLine("Invoking Memoizable Code");

     Type t = typeof(Test);
     Test objT = new Test();

     // Implement Memoization
     Dictionary<int, int> memoize = new Dictionary<int, int>();
     MethodInfo[] mi = t.GetMethods();
     foreach (MethodInfo m in mi)
     {
         foreach (Attribute a in m.GetCustomAttributes(false))
         {
             if (a is MemoAttribute)
             {
                 for (int i = 0; i < 2; i++)
                 {
                     int j;
                     if (memoize.TryGetValue(i, out j))
                     {
                         Debug.WriteLine("Remembered " + i);
                         continue;
                     }
                     else
                     {
                         j = (int) m.Invoke(objT, new object[]{i});
                         memoize[i] = j;
                         Debug.WriteLine("Memorized " + i);
                     }
                 }
             }
         }
     }
     Console.ReadLine();
 }

May be in comments you can suggest ways to implement a more generic Memo attribute (similar to Python’s @memo).