Algorithm matters !

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 :
[java]int[] used = new int [SIZE] ;

for (int i = 0; i < N; i++) { int start = starts [i] ; int end = ends [i] ; for (int j = start; j <= end; j++) { used [j]++ ; } }[/java] 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 :
[java]int[] used = new int [SIZE + 1] ; // HACK
for (int i = 0; i < N; i++) { used [starts [i]]++ ; used [ends [i] + 1]-- ; } int add = used [0] ; for (int i = 1; i < SIZE; i++) { add += used [i] ; used [i] = add ; }[/java] 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

3 thoughts on “Algorithm matters !”

  1. The speed difference depends of the mean distance between starts and ends, for large spreads the second code is always better. Often the speed depends of the data distribution !. For a vector processor the first one can be fast (add a scalar to a vector)

  2. To compare
    – on the CDC 7600 (1971)
    Ferrite type
    the central memory cycle=27,5ns
    the memory bandwidth=2Gbits/sec with 60 bits word
    – on the CDC CYBER 205 (1981)
    MOS type
    cycle=20ns
    memory bandwith=12,8Gbits/sec with 4 pipes and 64 bits word
    – on APPLE G5 (2004)
    DDR SDRAM type
    cycle=2,5ns
    bandwith=51 Gbits/sec with 2 words/cycle and 64 bits word

    The main evolution is the memory bandwitdh

Comments are closed.