[MUDDev] Event Scheduling
Cynbe ru Taren
cynbe at muq.org
Wed Feb 9 13:00:34 New Zealand Daylight Time 2000
HansHenrik Staerfeldt <hhs at cbs.dtu.dk> wrote:
 O(n log(log(n))), but i guess that was what you meant :)
Yes, the usual "As soon as I hit <RETURN>..." realization. :)
 > If it were that easy, quicksort would be history. :)

 It _is_ right :). Furthermore, i saw the eventqueue run as a sorter=20
 against quicksort, and the speedup _is_ there (for n>500 and random=20
 values, or so). I'll try and go dig up the reference.
Ok, I'll take a peek at it for grins.
But basically, sorts that are significantly faster than O( N log(N) )
are a lot like perpetual motion machines and angle trisections: The
theory is well enough understood that one doesn't really have to poke
through the details to know there is something fishy:
There are N! permutations of N distinct numbers, and any sort
which can honestly impose a total ordering on those has to
extract enough information to uniquely identify the input
permutation. That requires log2(N!) bits of information.
Using binary ops like < that produce a maximum of 1 bit of
information, this reduces to O( N * log(N) ) comparisons needed,
to a pretty good approximation. (Knuth demonstrates this via
Stirling's approximation to N!.)
Looking at it another way, given an initially symmetric set of N
objects, selecting a unique largest item from it requires log2( 1/N )
bits of information, directly from Shannon's definition of a bit of
information. Sorting the complete set thus requires
log2( 1/N ) + log2( 1/(N1) ) + log2( 1/(N2) ) + ...
which Knuth (Art of Computer Programming, Sorting and Searching 
I doublechecked this last night, but don't have it in front of me)
gives in closed form as
N * log(N)  2**(log(N)) +1
(with some ceiling operators omitted for clarity and courtesy of the
limits of ascii :) which he pretty unceremoniously approximates
immediately down to O( N * log(N) ). (I'm inclined to wonder if the
distinction isn't asymptotically somewhat significant when comparing,
say, quicksort and heapsort. But who am I?)
So honestly sorting N distinct numbers in asymptotically less than
O( N*log(N) ) time means Donald Knuth and Claude Shannon have made
a pretty horrible mathematical blunder somewhere. :)
There are ways of weaselling, of course, by subtly changing the terms
of the problem.
You can change the base of the log, and win a constant factor, by
using some op which generates more than one bit of information 
basically gives you radix sorts, if done honestly. (Done a bit
less honestly, gives you "constant time" sorts.)
You can also decide to keep the magnitude of the values being sorted
bounded while letting N grow without bound: This means you quickly
wind up not with N unique values, but instead with some fixed K of
unique values, and what you're really doing is sorting N values into K
bins. All you need do really is one linear scan through the array
incrementing one of K different counters for each entry checked. (For
clarity, think about "sorting" an array holding only 0 or 1 in each
slot. Easy, huh?)
There are probably also some other ways of subtly changing the
definition of the problem. :)
Knuth's writeup of all this is pretty convincing to simple minds
such as mine. He also covers quite a bit of cool stuff that I'd
completely forgotten about  I had fun skimming it again last
night. :) I wish I had time to reread the complete "book"...
Cynbe
_______________________________________________
MUDDev maillist  MUDDev at kanga.nu
http://www.kanga.nu/lists/listinfo/muddev
More information about the MUDDev
mailing list