February 2000
- datagram protocol design theory? (Question about multithreaded servers) Ola Fosheim Grøstad
- Library error J C Lawrence
- Semi-OT: Linux support in commercial MUDs? Ola Fosheim Grøstad
- From the Apache Referrer logs J C Lawrence
- From the Apache Referrer logs Kris Van Hees
- good muds for ai programming? Robert Zubek
- good muds for ai programming? J C Lawrence
- Event Scheduling Phillip Lenhardt
- Event Scheduling J C Lawrence
- Event Scheduling cg@ami-cg.GraySage.Edmonton.AB.CA
- Event Scheduling J C Lawrence
- Event Scheduling Phillip Lenhardt
- Event Scheduling J C Lawrence
- Event Scheduling Hans-Henrik Staerfeldt
- Event Scheduling Cynbe ru Taren
- Event Scheduling Hans-Henrik Staerfeldt
- Event Scheduling Cynbe ru Taren
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
| against quicksort, and the speedup _is_ there (for n>500 and random
| 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 - Event Scheduling Hans-Henrik Staerfeldt
- Event Scheduling Cynbe ru Taren
- Event Scheduling Miroslav Silovic
- Event Scheduling Jp Calderone
- Event Scheduling Ola Fosheim Grøstad
- Event Scheduling Miroslav Silovic
- Event Scheduling J C Lawrence
- Event Scheduling Cynbe ru Taren
- Event Scheduling Hans-Henrik Staerfeldt
- IO Speed Suggestions Christopher Kohnert
- IO Speed Suggestions J C Lawrence
- Couple of articles Koster, Raph
- Couple of articles Dr Richard A. Bartle
- OT: Soliciting advice from Canadians Alex Oren
- MUD Specific Building pages MichelleThompson
- MUD Specific Building pages J C Lawrence
- Embedding Python icecube@ihug.co.nz
- Embedding Python icecube@ihug.co.nz
- Embedding Python J C Lawrence
- Embedding Python Todd McKimmey
- Embedding Python Oliver Jowett
- Embedding Python Todd McKimmey
- ADMIN: List post rejections J C Lawrence
- distributed objects Kevin Littlejohn
- distributed objects Vijay Weasel Prabhakar
- distributed objects Brandon J. Rickman
- distributed objects J C Lawrence
- distributed objects Koster, Raph
- distributed objects Vijay Weasel Prabhakar
- distributed objects David Bennett
- distributed objects Phillip Lenhardt
- distributed objects cjones@one.net
- distributed objects F. Randall Farmer
- distributed objects Ola Fosheim Grøstad
- distributed objects Kevin Littlejohn
- distributed objects J C Lawrence
- distributed objects Gary Whitten
- distributed objects Balthazaar
- distributed objects J C Lawrence
- distributed objects Ola Fosheim Grøstad
- distributed objects Eli Stevens {Grey}
- distributed objects Jon A. Lambert
- distributed objects Charles Hughes
- distributed objects Caliban Tiresias Darklock
- distributed objects Charles Hughes
- distributed objects J C Lawrence
- distributed objects J C Lawrence
- distributed objects Charles Hughes
- distributed objects Charles Hughes
- distributed objects Laurent Bossavit
- distributed objects Kevin Littlejohn
- distributed objects markm@caplet.com
- distributed objects KevinL
- Distributed Objects Justin Rogers
- Security J C Lawrence
- commercial muds and cable TV (was code base inquiry ) Sellers, Michael
- commercial muds and cable TV (was code base inquiry ) Matthew Mihaly
- commercial muds and cable TV (was code base inq uiry ) Sellers, Michael
- commercial muds and cable TV (was code base inq uiry ) Matthew Mihaly
- business models Matthew Mihaly
- business models Daniel.Harman@barclayscapital.com
- business models Vincent Archer
- business models Dave Rickey
- a shrinking pool of players? Johan J Ingles-le Nobel
- a shrinking pool of players? Matthew Mihaly
- a shrinking pool of players? Sellers, Michael
- a shrinking pool of players? Bryce Harrington
- a shrinking pool of players? Travis S. Casey
- a shrinking pool of players? PartyG2816@aol.com
- a shrinking pool of players? J C Lawrence
- a shrinking pool of players? Sellers, Michael
- a shrinking pool of players? Sellers, Michael
- a shrinking pool of players? PartyG2816@aol.com
- a shrinking pool of players? Ryan P.
- a shrinking pool of players? J C Lawrence
- a shrinking pool of players? Koster, Raph
- a shrinking pool of players? Matthew Mihaly
- a shrinking pool of players? Koster, Raph
- a shrinking pool of players? Chris Turner
- a shrinking pool of players? Matthew Mihaly
- a shrinking pool of players? Chris Turner
- a shrinking pool of players? Draymoor
- a shrinking pool of players? Koster, Raph
- The Endeavour Map and MUD Applications Michael Hohensee
- The Endeavour Map and MUD Applications Ted Milker
- The Endeavour Map and MUD Applications David Bennett
- The Endeavour Map and MUD Applications Ted Milker
- The Endeavour Map and MUD Applications John Bertoglio
- The Endeavour Map and MUD Applications Justin Rogers
- The Endeavour Map and MUD Applications Eli Stevens {Grey}
- The Endeavour Map and MUD Applications John Bertoglio
- The Endeavour Map and MUD Applications Koster, Raph
- The Endeavour Map and MUD Applications Lo, Kam
- The Endeavour Map and MUD Applications Justin Rogers
- The Endeavour Map and MUD Applications Joel Dillon
- The Endeavour Map and MUD Applications Justin Rogers
- Next gen MUD wishlist Bryce Harrington
- Next gen MUD wishlist Bruce
- Next gen MUD wishlist Bryce Harrington
- Next gen MUD wishlist Bruce
- Next gen MUD wishlist J C Lawrence
- Next gen MUD wishlist Chris Jones
- Next gen MUD wishlist adam@treyarch.com
- Next gen MUD wishlist Sellers, Michael
- Next gen MUD wishlist adam@treyarch.com
- Next gen MUD wishlist Bruce
- Next gen MUD wishlist Bryce Harrington
- Codebase Ideas punitac@prodigy.net
- Codebase Ideas Bryce Harrington
- Codebase Ideas Aaron Mitchell
- OT: Money as motivator (was code base inquiry ) J C Lawrence
- OT: Money as motivator (was code base inquiry ) Matthew Mihaly
- Guide Applicant : Player Ratio Geoffrey A. MacDougall
- Guide Applicant : Player Ratio Matthew Mihaly
- MUD-Dev digest, Vol 1 #286 - 13 msgs Dr. Cat
- MUD-Dev digest, Vol 1 #286 - 13 msgs Caliban Tiresias Darklock
- MUD-Dev digest, Vol 1 #286 - 13 msgs Koster, Raph
- voice vs. text Matthew Mihaly
- voice vs. text Justin Rogers
- voice vs. text John Bertoglio
- voice vs. text Lovecraft
- voice vs. text Lo, Kam
- voice vs. text Hans-Henrik Staerfeldt
- Client side prediction Ola Fosheim Grøstad
- Client side prediction Koster, Raph
- Client side prediction Ola Fosheim Grøstad
- Client side prediction Justin Rogers
- Client side prediction Ola Fosheim Grøstad
- Client side prediction Koster, Raph
- Client side prediction Ola Fosheim Grøstad
- Dynamic help files, was code base inquiry Richard Woolcock
- OpenSource licenses for game rules? J C Lawrence
- To all the devoted! (fwd) J C Lawrence
- Newbies Johan J Ingles-le Nobel
- MUD-Dev digest, Vol 1 #288 - 9 msgs Dr. Cat
- (fwd) Commercial-use Restrictions on Code Bases (was: help me find 100% free graphical mud) J C Lawrence
- (fwd) ADMIN: "A Classification Of Muds" [was 'In defence of stock muds...'] J C Lawrence
- Distribution Geir Harald Hansen
- player persistence Matthew Mihaly
- [Off-topic] GDC-2000 Derek Snider
- [Off-topic] GDC-2000 J C Lawrence
- [Off-topic] GDC-2000 Justin Lockshaw
- [Off-topic] GDC-2000 Christopher Allen
- [Off-topic] GDC-2000 Matthew Mihaly
- [Off-topic] GDC-2000 Joe Andrieu
- [Off-topic] GDC-2000 Kristen L. Koster
- [Off-topic] GDC-2000 Richard A. Bartle
- [Off-topic] GDC-2000 Bruce
- [Off-topic] GDC-2000 David Bennett
- [Off-topic] GDC-2000 J C Lawrence
- [Off-topic] GDC-2000 J C Lawrence
- [Off-topic] GDC-2000 J C Lawrence
- [Off-topic] AAAI symposium (was: GDC-2000) Robert Zubek
- MSP Richard Ross
- Privateer-style mu*? Bobby Bailey
- Minimum community sizes Dan Root
- Minimum community sizes Koster, Raph
- Minimum community sizes Dan Root
- Minimum community sizes adam@treyarch.com
- Minimum community sizes Matthew Mihaly
- Minimum community sizes David Bennett
- Minimum community sizes Matthew Mihaly
- Pike codebase Daniel Podlejski
- chil@gate.net Joel Kelso