## Algorithms and optimization

No Language here - just algorithms!

Topic Author
prino
Registered Member
Posts: 61
Joined: Sun Jun 01, 2014 4:15 am
Location: Oostende, Belgium
Zodiac:

### Algorithms and optimization

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!

Robert AH Prins
Some z/OS code here

Anuj Dhawan
Founder
Posts: 2624
Joined: Sun Apr 21, 2013 7:40 pm
Location: Mumbai, India
Zodiac:

### Re: Algorithms and optimization

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

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

Thanks,
Anuj

Disclaimer: My comments on this website are my own and do not represent the opinions or suggestions of any other person or business entity, in any way.

Topic Author
prino
Registered Member
Posts: 61
Joined: Sun Jun 01, 2014 4:15 am
Location: Oostende, Belgium
Zodiac:

### Re: Algorithms and optimization

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.

Robert AH Prins
Some z/OS code here

passion56
New Member
Posts: 3
Joined: Fri May 20, 2016 9:48 pm

### Re: Algorithms and optimization

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

nicc
Global Moderator
Posts: 597
Joined: Wed Apr 23, 2014 8:45 pm