<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Event Scheduling -->
<!--X-From-R13: Qlaor eh Fnera <plaorNzhd.bet> -->
<!--X-Date: Tue, 08 Feb 2000 20:38:55 -0800 -->
<!--X-Message-Id: 200002082231.QAA15008#laurel,actlab.utexas.edu -->
<!--X-Content-Type: text/plain -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Re: [MUD-Dev] Event Scheduling</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:cynbe#muq,org">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg00286.html">Previous</a>
| <a href="msg00287.html">Next</a>
]
Thread:
[ <a href="msg00287.html">Previous</a>
| <a href="msg00289.html">Next</a>
]
Index:
[ <A HREF="author.html#00285">Author</A>
| <A HREF="#00285">Date</A>
| <A HREF="thread.html#00285">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Re: [MUD-Dev] Event Scheduling</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
<LI><em>Subject</em>: Re: [MUD-Dev] Event Scheduling</LI>
<LI><em>From</em>: Cynbe ru Taren <<A HREF="mailto:cynbe#muq,org">cynbe#muq,org</A>></LI>
<LI><em>Date</em>: Tue, 8 Feb 2000 16:31:24 -0600</LI>
<LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
<LI><em>Sender</em>: <A HREF="mailto:mud-dev-admin#kanga,nu">mud-dev-admin#kanga,nu</A></LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
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#kanga,nu
<A HREF="http://www.kanga.nu/lists/listinfo/mud-dev">http://www.kanga.nu/lists/listinfo/mud-dev</A>
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<ul compact><li><strong>Follow-Ups</strong>:
<ul>
<li><strong><A NAME="00289" HREF="msg00289.html">Re: [MUD-Dev] Event Scheduling</A></strong>
<ul compact><li><em>From:</em> Hans-Henrik Staerfeldt <hhs#cbs,dtu.dk></li></ul>
</UL></LI></UL>
<!--X-Follow-Ups-End-->
<!--X-References-->
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00286.html">Re: [MUD-Dev] Event Scheduling</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00287.html">Re: [MUD-Dev] Event Scheduling</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00287.html">Re: [MUD-Dev] Event Scheduling</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00289.html">Re: [MUD-Dev] Event Scheduling</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00285"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00285"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><STRONG>Re: [MUD-Dev] Event Scheduling</STRONG>, <EM>(continued)</EM>
<ul compact>
<ul compact>
<LI><strong><A NAME="00293" HREF="msg00293.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Phillip Lenhardt <a href="mailto:philen#funky,monkey.org">philen#funky,monkey.org</a>, Thu 10 Feb 2000, 17:23 GMT
<UL>
<LI><strong><A NAME="00294" HREF="msg00294.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
J C Lawrence <a href="mailto:claw#kanga,nu">claw#kanga,nu</a>, Thu 10 Feb 2000, 18:09 GMT
</LI>
</UL>
</LI>
</ul>
<LI><strong><A NAME="00286" HREF="msg00286.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
cg <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Wed 09 Feb 2000, 04:38 GMT
<UL>
<LI><strong><A NAME="00287" HREF="msg00287.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
J C Lawrence <a href="mailto:claw#kanga,nu">claw#kanga,nu</a>, Wed 09 Feb 2000, 04:53 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00285" HREF="msg00285.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Cynbe ru Taren <a href="mailto:cynbe#muq,org">cynbe#muq,org</a>, Wed 09 Feb 2000, 04:38 GMT
<UL>
<LI><strong><A NAME="00289" HREF="msg00289.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Hans-Henrik Staerfeldt <a href="mailto:hhs#cbs,dtu.dk">hhs#cbs,dtu.dk</a>, Wed 09 Feb 2000, 17:44 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00290" HREF="msg00290.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Cynbe ru Taren <a href="mailto:cynbe#muq,org">cynbe#muq,org</a>, Wed 09 Feb 2000, 19:02 GMT
<UL>
<LI><strong><A NAME="00295" HREF="msg00295.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Hans-Henrik Staerfeldt <a href="mailto:hhs#cbs,dtu.dk">hhs#cbs,dtu.dk</a>, Sun 13 Feb 2000, 00:10 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00302" HREF="msg00302.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Cynbe ru Taren <a href="mailto:cynbe#muq,org">cynbe#muq,org</a>, Sun 13 Feb 2000, 07:06 GMT
</LI>
</ul>
</LI>
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>