Archive

Posts Tagged ‘Algorithm’

Algorithm matters? Well it depends…

January 5th, 2005
No comments

On my previous post, I showed that using the best algorithm to solve a problem is very important. The example showed a nice algorithm 35x quicker thant the simple implementation. However, the post also says that the algorithm is not the only parameter in execution time.

I you recall the example, data are not read from a database or a file so the algorithm represents 100% of the computation time. In the real world, you would read data from outside and the computation would be far quicker than the retrieval. I've got another example of this principle. It will show beginners that they should'nt optimize too early and to advanced that they should focus on what's really taking time.

One of the first thing we learn on JAVA classes is recursion. We learn how to compute n! using recursion or standard for(;;) loop. Let's think of a piece of code that would give all words N letters long being of combination of L letters. We'll have to print L^N values (which can be a huge number). One can solve this problem with recursion of a standard loop with some kind of stack.

Here is the code:

PLAIN TEXT
JAVA:
  1. import java.util.* ;
  2.  
  3. public class Test
  4. {
  5.     private final static char[] letters = {'A', 'B', 'C', 'D'} ;
  6.     private final static int NB_CHOICES = letters.length ;
  7.     private final static int LEN = 10 ;
  8.        
  9.     public Test()
  10.     {
  11.     }
  12.  
  13.     private static void add (char[] aWord, int anIndex, Collection allWords)
  14.     {
  15.         if (anIndex == LEN)
  16.         {
  17.             //allWords.add (new String (aWord)) ;   // Found a word
  18.         }
  19.         else
  20.         {
  21.             for (int i = 0; i <NB_CHOICES; i++)
  22.             {
  23.                 aWord [anIndex] = letters [i] ;
  24.                 add (aWord, anIndex + 1, allWords) ;
  25.             }
  26.         }
  27.     }
  28.  
  29.     public Collection algo1()
  30.     {
  31.         char[] buf = new char [LEN] ;
  32.  
  33.         Collection allWords = new ArrayList() ;
  34.  
  35.         add (buf, 0, allWords) ;
  36.  
  37.         return allWords ;
  38.     }
  39.  
  40.     public Collection algo2()
  41.     {
  42.         Collection allWords = new ArrayList() ;
  43.  
  44.         char[] buf = new char [LEN] ;
  45.         int[] steps = new int [LEN] ;
  46.         int position = 0 ;
  47.  
  48.         do
  49.         {
  50.             int step = steps [position] ;
  51.    
  52.             if (step>= NB_CHOICES)
  53.             {
  54.                 if (--position>= 0)
  55.                 {
  56.                     steps [position]++ ;
  57.                 }
  58.             }
  59.             else
  60.             {
  61.                 buf [position] = letters [step] ;
  62.                 if ((position + 1) <LEN)
  63.                 {
  64.                     position++ ;
  65.                     steps [position] = 0 ;
  66.                 }
  67.                 else
  68.                 {
  69.                     //allWords.add (new String (buf)) ; // Found a word
  70.                     steps [position]++ ;
  71.                 }
  72.             }
  73.         }
  74.         while (position>= 0) ;
  75.  
  76.         return allWords ;
  77.     }
  78.  
  79.     public static void main (String[] args)
  80.     {
  81.         Test test = new Test() ;
  82.  
  83.         long date1 = System.currentTimeMillis() ;
  84.         Collection set1 = test.algo1() ;
  85.         long date2 = System.currentTimeMillis() ;
  86.         Collection set2 = test.algo2() ;
  87.         long date3 = System.currentTimeMillis() ;
  88.         System.out.println (date2 - date1) ;
  89.         System.out.println (date3 - date2) ;
  90.         System.out.println (set1.size()) ;
  91.         System.out.println (set2.size()) ;
  92.         System.out.println (set1.equals (set2)) ;
  93.     }
  94. }

Execution times on my machine :
recursion: 32ms
loop: 15ms

So the second algorithm is twice as fast with this set of values. However, if we need to create a new String() object for each word, we have these time:
recursion: 1610ms
loop: 1187ms
This is only a 26% gain.

So should we choose the second algorithm that is not easy to write nor to read or the first one?

Blog

Algorithm matters !

January 4th, 2005
2 comments

For a project, i had to write a piece of code that would count for each day of a year how many classrooms of a university are used. We know the start day of use and the end days of use for each classroom. There can be millions of use for periods from 1 day to the whole year. The first alogrithm is came up with was this one :

PLAIN TEXT
JAVA:
  1. int[] used = new int [SIZE] ;
  2.  
  3. for (int i = 0; i <N; i++)
  4. {
  5.     int start = starts [i] ;
  6.     int end = ends [i] ;
  7.  
  8.     for (int j = start; j <= end; j++)
  9.     {
  10.         used [j]++ ;
  11.     }
  12. }

Then I remembered some optimizing tips that my father's got from his job at Control Data years ago and I wrote this piece of code :

PLAIN TEXT
JAVA:
  1. int[] used = new int [SIZE + 1] ;   // HACK
  2. for (int i = 0; i <N; i++)
  3. {
  4.     used [starts [i]]++ ;
  5.     used [ends [i] + 1]-- ;
  6. }
  7.  
  8. int add = used [0] ;
  9. for (int i = 1; i <SIZE; i++)
  10. {
  11.     add += used [i] ;
  12.     used [i] = add ;
  13. }

The second code sample is 35x faster than the first one when SIZE is 365 and N is 10000000. The difference is huge but the time taken by the first code is still good enough. Memory access was more expensive on a Control Data machine than nowadays...

CDC 7600 Franlab Paris (1973) 5MBytes
CDC 7600 Franlab Paris (1973) 5 MBytes

CDC Cyber205 Minneapolis (1981) 32 MBytes
CDC Cyber205 Minneapolis (1981) 32 MBytes

Blog