Thursday, April 4, 2013

Optimization Of Nested For Loops

Hi Guys... In this post i am going to explain you that, how to write optimized nested for loops. Consider the following two nested for loops.

// Nested for loop-1
   for(a=0; a<20; a++)
   for(b=0; b<100; b++) 

// Nested for loop-2 
   for(c=0; c<100; c++)
   for(d=0; d<20; d++) 

 Both nested for loops gives same kind of functionality and the code in both nested for loops execute same number of times. Now let me ask one question :-)

which nested for loop is faster, loop-1 or loop-2?

You must be thinking, both execute in same time period. but actually not.

For Loop-1:

      
Number of post increment operations are: 20 X 100 + 20 = 2020;
       Number of comparisons are: [20 X 100 + 20] + 20 = 2040

For Loop-2:

     
Number of post increment operations are: 100 X 20 + 100 = 2100;
       Number of comparisons are: [100 X 20 + 100] + 100 = 2200

Conclusion:

If we compare both nested for loops w.r.t number of increment operations and comparisons, loop-1 is faster than loop-2. So, whenever we write nested for loops, it is better to choose the for loop, whose MAX_LIMIT is less than other as the first for loop.

for(a=0; a<MAX_LIMIT_A; a++)
for(b=0; b<MAX_LIMIT_B; b++)

Where MAX_LIMIT_A < MAX_LIMIT_B

Program to Test:

// File: loopCompare.c

#include<stdio.h>
void main()
{
  int comp_firstloop=0, incre_firstloop=0, comp_secondloop=0, incre_secondloop=0;
  int a, b, c, d;
   
  for(a=0; (++comp_firstloop) && a<20; a++, ++incre_firstloop)
  for(b=0; (++comp_firstloop) && b<100; b++, ++incre_firstloop);

  for(c=0; (++comp_secondloop) && c<100; c++, ++incre_secondloop)
  for(d=0; (++comp_secondloop) && d<20; d++, ++incre_secondloop);
  
  printf("\n #No. of Increment Operatiosn of 1st Nested For loop: %d", incre_firstloop);
  printf("\n #No. of comparison Operations of 1st Nested For loop: %d", comp_firstloop);

  printf("\n #No. of Increment Operations of 2nd Nested For loop: %d", incre_secondloop);
  printf("\n #No. of comparison Operations of 2nd Nested For loop: %d", comp_secondloop);
}

To Run:
gcc loopCompare.c
               ./a.out

OutPut:
 
#No. of Increment Operations of 1st Nested For loop: 2020
 #No. of comparison Operations of 1st Nested For loop: 2041
 #No. of Increment Operations of 2nd Nested For loop: 2100
 #No. of comparison Operations of 2nd Nested For loop: 2201

1 comment: