Algorithms and optimization

[prino]

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:

Code: Select all

NAT_SCAN        125,241   0.7952%
NAT_SCAN  1,815,960,038  98.8388%

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!

[Anuj Dhawan]

Moral of the story, first check your algorithm, and only then start thinking about optimisation!

Agree. An optimization tried around a bad algorithm, to start with, is not of much help.

And this is one of the reasons that we've a Forum dedicated to algorithms only.

[prino]

Current state @ 2016-08-01T19:08:

Statements executed to produce one table in the output dataset, current implementation

Code: Select all

NAT_SCAN       1,010,744

Old implementation:

Code: Select all

NAT_SCAN   3,443,933,405

Old implementation actually produces a FIXEDPOINTOVERFLOW in the PL/I library, but that can be prevented by adding a (NOFOFL): to the source.

[passion56]

you have covered that much of miles in hitchhiking? 3,443,933,405?

[nicc]

Please read carefully...

Statements executed