[MUD-Dev] Event Scheduling
hhs at cbs.dtu.dk
Fri Feb 11 12:12:31 New Zealand Daylight Time 2000
On Wed, 9 Feb 2000, Cynbe ru Taren wrote:
> 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=3D=
> | against quicksort, and the speedup _is_ there (for n>500 and random=3D=
> | 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=20
idea is that many of the operations you can do on todays computers=20
in practice is O(1), even though they operate on many parameters.=20
The assumption is that the size of the words in the registers is=20
O(log(n)), meaning that you need to represent the largest integers=20
(n) in these registers anyway. Thus the algorithms are limited by the
processer they run on, which is not entirely unreasonable.=20
Basically the algorithm discards of the 'comparison' paradigm to=20
gain better time. The assumption=20
"Using binary ops like < that produce a maximum of 1=20
bit of information"
Is the thing that is discarded (they mention this in the abstract)=20
Knuth's calculations hold, if you use that assumption!, so he's=20
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=20
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=20
the articles focus on shifts, or, and add being sufficient to do this=20
(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=20
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
> 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=E6rfeldt | bombman at diku.dk | work: hhs at cbs.dtu.dk=
address: |___ +45 40383492 __|__ +45 45252425 =
Dybendalsvej 74 2. th, | Scientific programmer at Center for Biological =
2720 Vanl=F8se, Danmark. | Sequence Analysis, Technical University of D=
MUD-Dev maillist - MUD-Dev at kanga.nu
More information about the MUD-Dev