Ryan Day

Nothing interesting has been happening lately. A few side projects that are neat, but other then that no new coding advancements. I was playing with memoization a bit. Of course, in my everyday job I have absolutely zero need for this. But maybe I will find something useful. I think that I could try to implement some advanced code techniques at work, but we would have to do things better first. Hundreds of different pages all using sql queries, no real structure. It gets mind bottling after awhile.

But anyways. To explore memoization, lets use my favorite advanced math algorithm interpreter, PHP. Then we will experiment in something new to me, C#!!!!

The fibonacci:

 PHP | 
 copy code |
?
 
1
function fib($c) {
2
   if( $c == 0 ) return 0;
3
   if( $c == 1 ) return 1;
4
   return fib($c-2) + fib($c-1);
5
}

Ok, so we have a nice recursive function to calculate the nth number in the fib sequence. Lets use it to calculate the 20th, 30th, and 40th numbers.

Start
6765: Time: 0.012
832040: Time: 1.178
63245986: Time: 135.191

Whoa, so times really start to add up quick. But we have to calculate this number or we get fired(this makes as much sense as anything else I do so I’m going to stick with it) and we have to calculate it quickly! We can use memoization on this fib() function to speed up the calls. This means that we will cache results as we calculate them, and then if we try to calculate the same number, we will grab the result from cache instead of running all the calculations again. This works because the results for fib(x) are always the same. There is no user input, time values, or any other real world nonsense getting in the way. We are going to add a static array to the fib() function, and store/retrieve the results from that array. Here is the code:

 PHP | 
 copy code |
?
 
1
function fib($c) {
2
   static $map;
3
   if( !is_array($map) ) $map = array();
4
   if( $c == 0 ) return 0;
5
   if( $c == 1 ) return 1;
6
   if( !isset($map[$c]) )        // Have we already calculated this?
7
   	$map[$c] = fib($c-2) + fib($c-1);
8
   return $map[$c];
9
}

We have a check to see if the request value has already been calculated. If not, we calculate it and store it. Then we return the stored version. This should speed things up. Lets run it again:

Start
6765: 0.001
832040: 0.002
102334155: 0.002

That is a serious improvement. It should be, we are only making 40 calls instead of the previous huge number. Now I just need to find a situation where this may be useful in my day to day programming.

What about a new language, C#? Lets run the same code again:

 C# | 
 copy code |
?
 
01
        static int fib(int x)
02
        {
03
            if (x < 2) return x;
04
            return fib(x - 2) + fib(x - 1);
05
        }
06
 
07
        static void Main(string[] args)
08
        {
09
            DateTime startTime = DateTime.Now;
10
            DateTime endTime;
11
            Console.WriteLine("Place 20: {0}", fib(20));
12
            endTime = DateTime.Now;
13
            Console.WriteLine("Time: {0}", startTime - endTime);
14
            Console.WriteLine("Place 30: {0}", fib(30));
15
            endTime = DateTime.Now;
16
            Console.WriteLine("Time: {0}", startTime - endTime);
17
            Console.WriteLine("Place 40: {0}", fib(40));
18
            endTime = DateTime.Now;
19
            Console.WriteLine("Time: {0}", startTime - endTime);
20
 
21
            Console.ReadKey();
22
        }

Note: I’m posting all the code on the off chance somebody reads my blog and would like bolster their self image by destroying my skills here. Look at the times though:

Place 20: 6765
Time: 00:00:00
Place 30: 832040
Time: -00:00:00.0901296
Place 40: 102334155
Time: -00:00:09.8040976

I mean, come on, 9 seconds as compared to PHP’s 135 seconds!? I’m running 2 virtual machines on my host machine with only 2 gigs of ram, listening to a podcast, and c# runs under windows of all things. Reality is shattering before my eyes.

Anyways. The goal here is to implement the map in C#. Obviously C# will scoff at trying to use key=>value arrays. I’ve come across a few different way to do this, and it looks like a Hashtable is the simplest.

 C# | 
 copy code |
?
 
1
        static Hashtable map;
2
 
3
        static int fib(int x)
4
        {
5
            if (x < 2) return x;
6
            if(!map.ContainsKey(x))
7
                map.Add(x, fib(x - 2) + fib(x - 1));
8
            return (int)map[x];
9
        }

Our times?

Place 20: 6765
Time: -00:00:00.0100144
Place 30: 832040
Time: -00:00:00.0100144
Place 40: 102334155
Time: -00:00:00.0100144

Not bad. There are some other ways to do this without the hashtable. You can use a ListCollection for example. But this seems like it works. Now to learn the more indepth aspects of hashtables in c#.