[MUD-Dev] Event Scheduling

[Cynbe ru Taren]

Hans-Henrik Staerfeldt wrote:
> I once saw a lecture covering an eventqueue algorithm running O(log(log(n)))
> for insertions and O(1) for deletions. My guess would be that it is the
> implementation of the actual events that will take the time, even if you
> use a O(log(n)) time event queue, or are my notions wrong?

I would take that O(log(log(n)) with a grain of salt: It means that
inserting and deleting N events gives you an O(log(log(n)) sort,
right?

If it were that easy, quicksort would be history. :)

Usually it turns out there's a bit of fudging, pretending that
radix sort is constant time, or some such, involved in such
expressions, at least in my experience.

Theoreticians like to cook up fanciful priority queues on a regular
basis:  They typically aren't anything for practicing programmers
to get overly excited about.  E.g., look up the "Calendar Queue",
which promises both O(1) insert and O(1) delete times.  It's basically
a rolling hashtable with the slots corresponding to times, and the
assumption that they hash uniformly enough to give the claimed
O(1), no doubt with the infamous "probability 1".

It may be apropos to point out yet again that it is almost always
a mistake to start optimizing this sort of stuff heavily before
you in fact have a demonstrated performance problem on live data,
and have traced it to the datastructure/algorithm in question?

 Cynbe



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