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
