[MUDDev] Event Scheduling
HansHenrik Staerfeldt
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:
>=20
> HansHenrik Staerfeldt <hhs at cbs.dtu.dk> wrote:
>=20
>  O(n log(log(n))), but i guess that was what you meant :)
>=20
> Yes, the usual "As soon as I hit <RETURN>..." realization. :)
>=20
>=20
>=20
>  > If it were that easy, quicksort would be history. :)
> 
>  It _is_ right :). Furthermore, i saw the eventqueue run as a sorter=3D=
20
>  against quicksort, and the speedup _is_ there (for n>500 and random=3D=
20
>  values, or so). I'll try and go dig up the reference.
>=20
> Ok, I'll take a peek at it for grins.
>=20
> 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) singlebit operations takes O(1) time on a computer,=
=20
f.inst. ORing 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 doublechecked 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 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"...
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=
enmark
_______________________________________________
MUDDev maillist  MUDDev at kanga.nu
http://www.kanga.nu/lists/listinfo/muddev
More information about the MUDDev
mailing list