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

One thought on “Memoization

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s