[MUD-Dev] Event Scheduling

[Hans-Henrik Staerfeldt]

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

>=20
> Hans-Henrik 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) single-bit operations takes O(1) time on a computer,=
=20
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
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=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|




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