|Re: 35s sorting routine challenge|
Message #2 Posted by Valentin Albillo on 25 July 2007, 9:02 a.m.,
in response to message #1 by Gene Wright
"Winner ought to be determined by the size x run time method used at HHC conferences."
May I suggest that, for practical, real-life purposes other criteria would be more useful, namely (a) The shortest routine, running time a secondary consideration within reason, and (b) The fastest routine, size a secondary consideration, again within reason.
The rationale is that, usually, you are either constrained for space (because you need to be capable to process as much data as possible) in which case you'll certainly want to minimize program size above all, or else you're not specially constrained for space, in which case you'll want your sort to proceed as fast as possible.
The size x run time criterium seems to me to fulfill neither of those practical requirements and it was probably used just to ease the judges' cumbersome and difficult task of objectively selecting a winner.
As such, I'll propose that people accepting the challenge would submit either one or two routines, each individually optimized for the speed/size criteria.
That's certainly what I'll do, as my primary goal is to produce maximally useful routines, not winning challenges. :-)
P.S.: Sorting methods also greatly vary in performance depending on the nature of the data being sorted, i.e., some methods that are nearly optimal for quasi-random data may perform abysmally if the data are already almost sorted or reverse-sorted.
So I would suggest that timings should be given for:
- A random-data array, generated by using the HP35S' built-in random-number
function starting from the seed Pi. This will guarantee repeatability and the same array for everyone.
- A perfectly sorted array: 1, 2, 3, ..., n
- A perfectly reverse-sorted array: n, n-1, ..., 3, 2, 1
- An array with all elements equal: 1, 1, 1, ... , 1
I guess many participants will find that their routine does well with some of the array types but not so well with others. Depending on the real-life application this might be important, as having data which is almost perfectly sorted to begin with is quite common, actually.
Best regards from V.
Edited: 25 July 2007, 9:13 a.m.