Introduction:
Writing efficient code is a very important task of any developer. Unfortunately, most of the time we concentrate so much on writing correct code,that we forget the other important aspect if it. And that is making sure that the code we have written is efficient. A lot of techniques can be followed to write efficient code. A brief overview of these techniques has been given. After these techniques,an important algorithm - Generation of the Fibonacci Sequence has been written in an efficient manner.
Code Optimization Techniques
1.Combine loops, which operate over the same range of values:
for ( k=1 to n ) { initialize T[k]; }
for ( m=1 to n ) { Max[m]=m*Max[m]; }
The above two loops can be easily combined into one as follows:
for ( k=1 to n ) {
initialize T[k];
Max[k]=k*Max[k];
}
2. Use constants of the correct type. Type conversions are sometimes expensive
3. Precompute results whereever necessary
In a lot of situations, it is better to precompute results. It is usually best to do this in case a fixed set of results are accessed very frequently. e.g. The results of a tax saving calculation formula can be put up in a lookup table. Whenever any result is required, it can be directly accessed from the table rather than computing it everytime
4. Unrolling loops is another way of optimizing the code. It can be done in a lot of situations.
e.g.
i=1;
while(i<=num) {
a[i]=i;
i=i+1;
}
The above loop can be unrolled in the following way:
i=1;
while(i
a[i]=i;
a[i+1]=i+1;
i=i+2;
}
5. Minimize work performed inside loops. Perform constant expression evaluations and function calls outside the loop. Avoid extra variables if they are not required
e.g.
i=1;
k=45;
while(i<=num) {
t=pow(10,3)*sqrt(k);
a[i]=i*t;
i=i+1;
}
The above code can be efficiently written as
i=1;
k=45;
t=pow(10,3)*sqrt(k);
while(i<=num) {
a[i]=i*t;
i=i+1;
}
6. Unswitch loops that contain if tests, if these tests do not change inside the loop
e.g.
day=1;
while(i<=num) {
if(day==1)
{
printf("Monday");
}
a[i]=i*10;
i=i+1;
}
The above code can be efficiently written as
day=1;
while(i<=num) {
printf("Monday");
a[i]=i*10;
i=i+1;
}
7. Use sentinels in loop
This is usually done in case of a search loop that looks up an element in a list. It is useful as it eleminates the need for checking whether the end of the list has been reached
e.g.
i=1;
while((a[i] !=key)&&(i<=num)) {
i=i+1;
}
if(a[i]==key)
printf("key found");
The above code can be efficiently written as
i=1;
a[num]=key;
while(a[i]!=key) {
i=i+1;
}
if((a[i]==key)&&(i !=num))
printf("key found");
8. Reduce the strength of operations performed inside loops i.e. replace operations such as multiplication by cheaper ones as addition.
e.g.
for(i=1 to num) {
comm[i]=i * Rev * BaseComm * Disc ;
i=i+1;
}
The above code can be efficiently written as
commstart=Rev * BaseComm * Disc ;
comm[1]=commstart ;
for(i=2 to num) {
comm[i]=comm[i-1] + commstart ;
i=i+1;
}
9. Stop testing when you know the answer.
e.g.
NegativeFound=FALSE;
for(i=1 to Max) {
if (array[i]<0) {
NegativeFound=TRUE;
}
i=i+1;
}
print NegativeFound
The above code can be efficiently written as
NegativeFound=FALSE;
for(i=1 to Max) {
if (array[i]<0) {
NegativeFound=TRUE;
break;
}
i=i+1;
}
print NegativeFound
10. Order tests in case statements and if-else chains by frequency
e.g.
if(marks>=90)
printf("Excellent");
elseif(marks>=80 && marks <90)
printf("Good")
elseif(marks>=70 && marks <80)
printf("Fair")
elseif(marks>=60 && marks <70)
printf("Average")
else
printf("Poor")
Let us say that we know that the probability of getting marks is of the order: average > fair> good > excellent > poor. Then, The above code can be efficiently written as
if(marks>=60 && marks <70)
printf("Average");
elseif(marks>=70 && marks <80)
printf("Fair")
elseif(marks>=80 && marks <90)
printf("Good")
elseif(marks>=90)
printf("Excellent")
else
printf("Poor")
11. Minimize array references - if a constant array element is repeatedly referred to inside a loop, move it out
e.g.
for(i=1,k=1; i<=Max;i++,k++) {
total[i]=array[1]+array[i];
}
The above code can be efficiently written as
constval=array[1];
for(i=1,k=1; i<=Max;i++,k++) {
total[i]=constval+array[i];
}
12. Augment data structures with indexes
e.g. An index for a sorted linked list can speed up an otherwise strictly linear search
13. Exploit algebraic identities.
e.g.
if(sqrt(x) > sqrt(y) )
print x
else
print y
}
The above code can be efficiently written as
if(x > y )
print x
else
print y
}
14. Reduce strength in logical and mathematical expressions. It can be done by taking out common factors (to reduce strength of computations).
e.g.
Ax3 + Bx2 + Cx + D can be better evaluated as ((Ax+B)x+C)x+D .
15. Be wary of system routines
Now, I will give a full fledged example of "Generation of Fibonacci sequence " and explain how by using one of the above techniques - technique No. 5, we can write an efficient algorithm Generation of the Fibonacci Sequence
Fibonacci Sequence is a sequence of the form
0,1,1,2,3,5,8,13...,
This sequence has practical applications in botany,electrical network theory, sorting and theory,etc.
Correct but Inefficient Algorithm
A correct, although inefficient algorithm, which is normally used is as follows:
var firstTerm;
var secondTerm;
var nextTerm;
var NoOfTerms;
var i;
begin
firstTerm=0;
secondTerm=1;
i=2;
writeln('Enter the number of Fibonacci terns to be generated');
readln(noOfTerms);
if(noOfTerms>=1)
writeln(firstTerm)
if(noOfTerms>=2)
writeln(secondTerm)
while ( i < NoOfTerms )
begin
i=i+1;
nextTerm=firstTerm+secondTerm;
firstTerm=secondTerm;
secondTerm=nextTerm;
writeln(nextTerm);
end;
end;
But there is a way by which we can make an important improvement to our algorithm. And that is by removing the need for using the extra variable - nextTerm. This will greatly help in making the algorithm efficient. To make this possible, what we attempt to do is to make the two variables firstTerm and secondTerm always relevant. By implementing these changes, we get an efficient algorithm as follows:
var firstTerm;
var secondTerm;
var NoOfTerms;
var i;
begin
firstTerm=0;
secondTerm=1;
i=2;
writeln('Enter the number of Fibonacci terns to be generated');
readln(noOfTerms);
while ( i < NoOfTerms )
begin
writeln(firstTerm,secondTerm);
firstTerm=firstTerm+secondTerm;
secondTerm=firstTerm+secondTerm;
i=i+2;
end;
if(i==NoOfTerms)
writeln(firstTerm,secondTerm);
else
writeln(firstTerm);
end;
Conclusion
Efficient code can be written using a lot of code optimization techniques
