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
