Re: Sort items in a list without OSAXen
Re: Sort items in a list without OSAXen
- Subject: Re: Sort items in a list without OSAXen
- From: Emmanuel <email@hidden>
- Date: Wed, 5 Sep 2001 23:42:08 +0200
Recently I reported some timing results of different "sort" routines.
The results about "SortedRefNumbers" that you saw here are irrelevant.
They have been made wrong as a consequence of a fundamental bug introduced
in AppleScript by OS 9 about how references are handled. I comment this bug
in a separate post. Note that this bug is very likely to be implied in the
oddities observed by Arthur with SortedRefNumbers.
As an erratum, here is the summary of our comparisons of "sort" handlers on
lists of random integers.
size = size of the list (random integers in the range 1 - 500)
SRN = "SortedRefNumbers" (Arthur's)
s = "sort" (Smile's)
SN = "SortedNumbers" (Arthur's)
Timings = milliseconds, performed on a Pismo under 0S9.1. Average over 1 to
5 runs.
size s SRN SN
------------------------------
50 50 213 207
100 137 747 1200
200 1203 2833 8160
500 1583 16867 111883
(caution! timings highly variable depending upon the draw of the original list)
- the fastest, even for short lists, is Smile's "sort"
- Smile's "sort" scales like N^2
- Arthur's "SortedNumbers" scales like N^3
- small improvements (e.g.: "set i to contents of i") speed Smile's "sort"
by approx. x2
- Smile's "sort" scales as N^2 because accessing any item of a list scales
like the size of the list. In other words, Smile's "sort" CPU time is
eventually dominated by: "repeat with i in l - set i to contents of i",
which scales like N^2. This can be easily worked around - at a cost of a
routine become enormous and hideous - so it should be feasable to
eventually design a "sort" handler scaling like N.Log(N).
The issue is, are we able to sort a list of ca.1000 items in a few seconds,
or not.
Best regards,
Emmanuel