While reading an algorithms book, I learned that minor optimizations and choosing right algorithm can improve the code performance drastically. In this post we will see how this is happening.

Consider the following trivial code to calculate a Fibonacci value of a number using recursion.

int fibonacci(int num)

{

if (num <= 1)
return num;
else
return fibonacci(num - 1) + fibonacci(num - 2);
}
[/sourcecode]
Here is how this code executes for `fibonacci(5)`

.

A big tree for such a small number!

Note that the nodes that are marked in red color are executed multiple times. This small algorithm calculates `fibonacci(3)`

and `fibonacci(2)`

multiple times which is unnecessary. When the numbers passed to this functions gets bigger, the recursion tree and number of multiple calculations will also grow.

`fibonacci(45)`

took `01 minute 02 seconds and 1538874 ms`

on my machine.

Avoiding the multiple calculations of same number is the way to optimize this code. When each value is calculated, it should be cached. So the value can be reused without recomputing. We need to use a data structure that supports faster item lookups. A `Dictionary(TKey,TValue)`

will be obvious data structure as it allows searches in `O(1)`

complexity.

Here is a modified code.

Dictionary

int optimized_fibonacci(int num)

{

int computedFib;

if (num <= 1)
return num;
else if (cache.TryGetValue(num, out computedFib))
return computedFib; // returning cached value and avoiding computation
else
{
// calculating and caching
computedFib = optimized_fibonacci(num - 1) + optimized_fibonacci(num - 2);
cache.Add(num, computedFib);
}
return computedFib;
}
[/sourcecode]
This code calculates `fibonacci(45)`

in just 41Ms on my machine!

Nice one 🙂