Algorithms and optimization

No Language here - just algorithms!
Previous topicNext topic
User avatar

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

Algorithms and optimization

Post by prino » 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:

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
robertahprins @ the.17+Gb.Google thingy
Some z/OS code here

User avatar

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

Re: Algorithms and optimization

Post by Anuj Dhawan » Sun Jun 01, 2014 10:56 pm

prino wrote: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.


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.

User avatar

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

Re: Algorithms and optimization

Post by prino » Wed Sep 14, 2016 11:58 am

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
robertahprins @ the.17+Gb.Google thingy
Some z/OS code here


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

Re: Algorithms and optimization

Post by passion56 » Wed Sep 14, 2016 1:43 pm

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




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

Re: Algorithms and optimization

Post by nicc » Wed Sep 14, 2016 3:52 pm

Please read carefully...
Statements executed


Regards
Nic

Previous topicNext topic

Return to “Programming Algorithms.”