Saturday, July 21, 2007

Highly Efficient Code

Let's consider a function written in C# that computes the sum of the integers from 1 to 1000. There are several ways to write such a function and the choice you make may depend on what is important for the given application and your skill as a programmer. What is important might include the size of the code, how fast the code executes, how much it costs to write the code, and how easy it is to modify. Consider this approach:

int Sum1to1000()
{
int sum = 0;
sum = sum + 1;
sum = sum + 2;
sum = sum + 3;

(995 lines of code not shown)

sum = sum + 999;
sum = sum + 1000;
return sum;
}

This is the brute force approach, and though it has one advantage, almost no one would write the function in this way. Now consider this approach:

int Sum1to1000()
{
int sum = 0;
for (i=1; i<=1000; i++)

sum = sum + i;
return sum;
}

This second approach is typical of how most programmers would write the function. Only four lines of code are required so it takes less code and, more importantly, cost fewer engineering dollars to write. The down side of this function is that it takes about 3 times as long to execute as the first function. The first function only requires the computer to perform 1000 additions, while the second function performs 2000 additions and 1000 comparisons. However, we are talking about an excecution time of less than a millisecond -- so who cares if the first function is faster. We would rather save engineering dollars.

The second function's design is also superior because it can be easily modified into a more general purpose function, like the one below. If your initial design was like the first function you would have to completely abandon the design in order to write this more general purpose function.

int SumConsecutiveIntegers(int first, int last)
{
int sum = 0;
for (int i=first; i<=last; i++)

sum = sum + i;
return sum;
}

Now a more innovative programmer might take advantage of the fact that 1001 = 1+1000 = 2+999 (etc) and write the function as follows:

int Sum1to1000()
{
return 1001 * 500;
}

This function is thousands of times faster than the second function and requires only one line of code. It's also easily modified and its general purpose equivalent looks like this:

int SumConsecutiveIntegers(int first, int last)
{
return (first + last) * (last-first+1) / 2;
}


This is an example of highly efficient code. We could only get faster by going to assembly language and performing a binary shift instead of a division.

What I have said here is hardly profound and has been dumbed down to make it easier for the layman to understand. My purpose was just to explain what I meant by highly efficient code in my post about junk DNA.