[MUD-Dev] Event Scheduling

[Cynbe ru Taren]

Hans-Henrik 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/(N-1) ) + log2( 1/(N-2) ) + ...

which Knuth (Art of Computer Programming, Sorting and Searching --
I double-checked 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 write-up 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



_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev