Algorithms and optimization
Posted: Sun Jun 01, 2014 7:55 pm
I hitchhike, and being a programmer, the notes I make while hitchhiking end up in a file that is subsequently processed by a program to produce a truckload of amusing statistics. One of the tables contains the minimum number of rides (M) I needed to be picked up by drivers of N different nationalities. Obviously, the number of rides increases as N increases, getting drivers of two different nationalities in two consecutive rides is so common that I've specifically excluded this, and even 3-in-3, which happened 184 times in my 3,190 rides is pretty common, but after one last occasion where M equals N (8-in-8(!)), M starts to outpace N, and reaches 2,861 for 82 nationalities.
I added this table at the end of 1996 (1996-12-28) to my PL/I version of the program (the PC version is written in Pascal with an unhealthy amount of code converted into assembler), and the algorithm was quite smart, or so I thought. Working in the Netherlands at the time, at a site where I could use Strobe, I soon realized that my "quite smart" algorithm was not very smart at all, despite all the optimizations had had come up with, but couldn't think of anything better.
So in 1998 I asked around in the comp.lang.pascal.borland Usenet group, and soon after I got two better versions. I don't have the Strobe report any more, but occasionally I compile the old AD 1998 program with the PL/I "COUNT" option and the results are pretty shocking, when compared to the current implementation:
The counts are the number of statements executed in the procedure, the percentages are the percentage of the total number of statements executed in the entire program. Using a better algorithm, the number of statements executed in "NAT_SCAN" has been reduced by 99.993%...
Moral of the story, first check your algorithm, and only then start thinking about optimisation!
I added this table at the end of 1996 (1996-12-28) to my PL/I version of the program (the PC version is written in Pascal with an unhealthy amount of code converted into assembler), and the algorithm was quite smart, or so I thought. Working in the Netherlands at the time, at a site where I could use Strobe, I soon realized that my "quite smart" algorithm was not very smart at all, despite all the optimizations had had come up with, but couldn't think of anything better.
So in 1998 I asked around in the comp.lang.pascal.borland Usenet group, and soon after I got two better versions. I don't have the Strobe report any more, but occasionally I compile the old AD 1998 program with the PL/I "COUNT" option and the results are pretty shocking, when compared to the current implementation:
Code: Select all
NAT_SCAN 125,241 0.7952%
NAT_SCAN 1,815,960,038 98.8388%
Moral of the story, first check your algorithm, and only then start thinking about optimisation!