Nice comment. Recently I did a benchmark, and discovered much to my surprise that a 1.5*n algorithm in C to find the min and the max is slower by a factor of 4 than a more straightforward 2*n algorithm (just (>./x),<./x). I believe this is due to the C compiler being able to optimize the straightforward loop that implements >./x , and less so the more complicated loop for the 1.5*n algorithm.
----- Original Message ----- From: Henry Rich <[email protected]> Date: Sunday, November 14, 2010 20:06 Subject: Re: [Jprogramming] optimal algorithm in interpreted language To: Programming forum <[email protected]> > When Philip II of Macedon (father of Alexander) wanted to humble > the > Spartans, he sent an ambassador who said: > > You are advised to submit without further delay, for if my king > brings > his army into your land, he will destroy your farms, slay your > people, > and raze your city. > > To which the Spartans replied: > > If. > > > In a Laconic mood, I say, > > optimal? > > So many things happen in a modern CPU: instruction caches, data > caches, > main memory. The comparison takes 1 lousy CPU cycle and is > totally > immaterial (it's overlapped with the rest of the processing). > > Henry Rich > > On 11/14/2010 10:27 PM, David Ward Lambert wrote: > > The optimal algorithm to find minimum and maximum of a list uses > > 1.5*#list comparisons. It compares 2 items of the > list then tests only > > the smaller of these against current smallest, and only the > greater of > > the pair against current maximum. Here I present a "j-ish" > > implementation of the optimal algorithm 1000 times worse > than>./ -<./ > > It puts the minimum candidates into column 0, the maximum candidates > > into column 1, then scans the appropriate columns > independently for > > smallest and greatest. Perhaps the optimal minmax in an > interpreted> language is reasonable only when the comparison > function is expensive? > > Code for odd length list omitted. > > > > data =: 1e6 ?...@$ 2e6 > > > > ts'range data' NB. > 2.0*#y comparisons > > 0.004465 2048 > > > > ts'Range data' NB. > 1.5*#y comparisons "optimal" > > 0.412091 2.51726e7 > > > > (range = Range) data > > 1 > > > > Range > > r@:sort_pairs > > > > sort_pairs > > _2&(/:~\) > > > > r > >> ./@:(_1&{."1) -<./@:(1&{."1) > > > > range > >> ./ -<./ > > > > > > --------------------------------------------------------------- > ------- > > For information about J forums see > http://www.jsoftware.com/forums.htm> > ----------------------------------------------------------------- > ----- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
