Re: [MUD-Dev] Event Scheduling

[Hans-Henrik Staerfeldt <hhs#cbs,dtu.dk>]

On Wed, 9 Feb 2000, Cynbe ru Taren wrote:

> 
> Hans-Henrik Staerfeldt <hhs#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.
> 
> 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!.)

Ah, but this is why this is done on a 'practcal RAM machine'. The 
idea is that many of the operations you can do on todays computers 
in practice is O(1), even though they operate on many parameters. 
The assumption is that the size of the words in the registers is 
O(log(n)), meaning that you need to represent the largest integers 
(n) in these registers anyway. Thus the algorithms are limited by the
processer they run on, which is not entirely unreasonable. 

Basically the algorithm discards of the 'comparison' paradigm to 
gain better time. The assumption 

   "Using binary ops like < that produce a maximum of 1 
    bit of information"

Is the thing that is discarded (they mention this in the abstract) 
Knuth's calculations hold, if you use that assumption!, so he's 
very right :-)

Now, making log_2(N) single-bit operations takes O(1) time on a computer, 
f.inst. OR-ing two words will perform log_2(n) OR operations in what 
is the minimum time for any operation the computer can do O(1). Some
argue that some operations are more complex than others, thus some of 
the articles focus on shifts, or, and add being sufficient to do this 
(i think they call it AC0 operations).

These are some of the operators they use for better speed.

This model only breaks if you want to run with arbitrary precition 
numbers, and things like that.

> 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

You do indeed reference the right people :-). Again, this is under the
comparison assumption.

> There are ways of weaselling, of course, by subtly changing the terms
> of the problem.

Yes, they change the basis of the ability of the computer from a
turing machine to something closer resembling todays computers, and
by not using comparison in the usual sense.

> 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"...

Oh, Knuth is very right, given his assumption :-)

Hans Henrik Stærfeldt   |    bombman#diku,dk    | work:  hhs#cbs,dtu.dk      |
address:                |___  +45 40383492    __|__       +45 45252425     __|
 Dybendalsvej 74 2. th, | Scientific programmer at Center for Biological     |
 2720 Vanløse, Danmark. |  Sequence Analysis, Technical University of Denmark|




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