How small code optimizations can improve the performance and storage requirements

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

Recursion tree for calculating fibonocci(5)

Recursion tree for calculating fibonocci(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 cache = new 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!

Advertisements

One thought on “How small code optimizations can improve the performance and storage requirements

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