<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Event Scheduling -->
<!--X-From-R13: Qlaor eh Fnera <plaorNzhd.bet> -->
<!--X-Date: Wed, 09 Feb 2000 11:02:40 -0800 -->
<!--X-Message-Id: 200002091900.NAA20528#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="msg00289.html">Previous</a>
| <a href="msg00291.html">Next</a>
]
Thread:
[ <a href="msg00289.html">Previous</a>
| <a href="msg00295.html">Next</a>
]
Index:
[ <A HREF="author.html#00290">Author</A>
| <A HREF="#00290">Date</A>
| <A HREF="thread.html#00290">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>: Wed, 9 Feb 2000 13:00:34 -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 <hhs#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=20
| against quicksort, and the speedup _is_ there (for n>500 and random=20
| values, or so). I'll try and go dig up the reference.
Ok, I'll take a peek at it for grins.
But basically, sorts that are significantly faster than O( N log(N) )
are a lot like perpetual motion machines and angle trisections: The
theory is well enough understood that one doesn't really have to poke
through the details to know there is something fishy:
There are N! permutations of N distinct numbers, and any sort
which can honestly impose a total ordering on those has to
extract enough information to uniquely identify the input
permutation. That requires log2(N!) bits of information.
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!.)
Looking at it another way, given an initially symmetric set of N
objects, selecting a unique largest item from it requires log2( 1/N )
bits of information, directly from Shannon's definition of a bit of
information. Sorting the complete set thus requires
log2( 1/N ) + log2( 1/(N-1) ) + log2( 1/(N-2) ) + ...
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
N * log(N) - 2**(log(N)) +1
(with some ceiling operators omitted for clarity and courtesy of the
limits of ascii :) which he pretty unceremoniously approximates
immediately down to O( N * log(N) ). (I'm inclined to wonder if the
distinction isn't asymptotically somewhat significant when comparing,
say, quicksort and heapsort. But who am I?)
So honestly sorting N distinct numbers in asymptotically less than
O( N*log(N) ) time means Donald Knuth and Claude Shannon have made
a pretty horrible mathematical blunder somewhere. :)
There are ways of weaselling, of course, by subtly changing the terms
of the problem.
You can change the base of the log, and win a constant factor, by
using some op which generates more than one bit of information --
basically gives you radix sorts, if done honestly. (Done a bit
less honestly, gives you "constant time" sorts.)
You can also decide to keep the magnitude of the values being sorted
bounded while letting N grow without bound: This means you quickly
wind up not with N unique values, but instead with some fixed K of
unique values, and what you're really doing is sorting N values into K
bins. All you need do really is one linear scan through the array
incrementing one of K different counters for each entry checked. (For
clarity, think about "sorting" an array holding only 0 or 1 in each
slot. Easy, huh?)
There are probably also some other ways of subtly changing the
definition of the problem. :)
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"...
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="00295" HREF="msg00295.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="msg00289.html">Re: [MUD-Dev] Event Scheduling</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00291.html">RE: [MUD-Dev] Couple of articles</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00289.html">Re: [MUD-Dev] Event Scheduling</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00295.html">Re: [MUD-Dev] Event Scheduling</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00290"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00290"><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>
<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
<UL>
<LI><strong><A NAME="00307" HREF="msg00307.html">Re: [MUD-Dev] Event Scheduling</A></strong>,
Hans-Henrik Staerfeldt <a href="mailto:hhs#cbs,dtu.dk">hhs#cbs,dtu.dk</a>, Mon 14 Feb 2000, 17:21 GMT
</LI>
</UL>
</LI>
</ul>
</LI>
<LI><strong><A NAME="00271" HREF="msg00271.html">[MUD-Dev] good muds for ai programming?</A></strong>,
Robert Zubek <a href="mailto:rob#ils,nwu.edu">rob#ils,nwu.edu</a>, Sun 06 Feb 2000, 01:33 GMT
</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>