March 1999
- Storytelling vs simulation, Koster, Raph
- Storytelling vs simulation, Eli Stevens {KiZurich}
- Storytelling vs simulation, Mik Clarke
- Storytelling vs simulation, J C Lawrence
- Storytelling vs simulation, Matthew Mihaly
- Storytelling vs simulation, J C Lawrence
- Storytelling vs simulation, Matthew Mihaly
- Storytelling vs simulation, Caliban Tiresias Darklock
- OT: MUSH semantics (was: Influential muds) T. Alexander Popiel
- Storytelling and Gods (fairly long) Matthew Mihaly
- Storytelling and Gods (fairly long) Koster, Raph
- Storytelling and Gods (fairly long) Matthew Mihaly
- Generic event handling Adam Wiggins
- How to support 1000+ simultaneous connections, and some philosophy. Ben Greear
- How to support 1000+ simultaneous connections, and some philosophy. Matthew D. Fuller
- How to support 1000+ simultaneous connections, and some philosophy. Chris Gray
- How to support 1000+ simultaneous connections, and some philosophy. Chris Gray
- How to support 1000+ simultaneous connections, and some philosophy. Caliban Tiresias Darklock
- How to support 1000+ simultaneous connections, and some philosophy. Nathan F Yospe
- How to support 1000+ simultaneous connections, and some philosophy. Caliban Tiresias Darklock
- How to support 1000+ simultaneous connections, and some philosophy. Jason Spangler
- How to support 1000+ simultaneous connections, and some philosophy. Oliver Jowett
- How to support 1000+ simultaneous connections, and some philosophy. Oliver Jowett
- How to support 1000+ simultaneous connections, and some philosophy. Chris Gray
- How to support 1000+ simultaneous connections, and some philosophy. Caliban Tiresias Darklock
- How to support 1000+ simultaneous connections, and some philosophy. Chris Gray
- How to support 1000+ simultaneous connections, and some philosophy. Petri Virkkula
- How to support 1000+ simultaneous connections, and some philosophy. Chris Gray
- How to support 1000+ simultaneous connections, and some philosophy. Petri Virkkula
- How to support 1000+ simultaneous connections, and some philosophy. J C Lawrence
- How to support 1000+ simultaneous connections, and some philosophy. Petri Virkkula
- ADMIN: Kanga.Nu outage and other news -- please read J C Lawrence
- Elder Games Martin C Sweitzer
- Elder Games Adam Wiggins
- Elder Games Koster, Raph
- Elder Games Matthew Mihaly
- Elder Games Caliban Tiresias Darklock
- Elder Games Martin C Sweitzer
- Elder Games Matthew Mihaly
- Elder Games Kylotan
- Elder Games Caliban Tiresias Darklock
- Elder Games Kylotan
- Elder Games Koster, Raph
- Elder Games B. Scott Boding
- Elder Games Wes Connell
- Elder Games Caliban Tiresias Darklock
- Elder Games Matthew D. Fuller
- Elder Games B. Scott Boding
- Elder Games Michael Hohensee
- Elder Games Matthew Mihaly
- Elder Games Benjamin D. Wiechel
- Elder Games Chris Gray
- Elder Games Chris Gray
- Elder Games J C Lawrence
- Elder Games Nathan F Yospe
- Elder Games J C Lawrence
- Multiple clients (was How to support 1000+ simultaneous connections) Matthew D. Fuller
- Multiple clients (was How to support 1000+ simultaneous connections) Chris Gray
- Naming and Directories? Mark Gritter
- Naming and Directories? Matthew D. Fuller
- Naming and Directories? Adam Wiggins
- Naming and Directories? Hans-Henrik Staerfeldt
- Naming and Directories? Chris Gray
- Naming and Directories? Mark Gritter
- Naming and Directories? Mik Clarke
- Naming and Directories? Mark Gritter
- Naming and Directories? Nathan F Yospe
- Naming and Directories? Ola Fosheim Grøstad
- Naming and Directories? Nathan F Yospe
- Naming and Directories? Mik Clarke
- Naming and Directories? Mark Gritter
Mik Clarke writes:
>
> Mark Gritter wrote:
> > Hans Staerfeldt suggest "search tries" in his response to my original e-mail.
> > The idea is that each node stores a name and 26 pointers to child nodes. The
> > tree is searched by using successive letters as an index to the array of
> > pointers. You can search for abbreviations easily in this scheme--- if
> > you run out of letters and the node has only one child, you've found the
> > full name.
>
> Ummm. Yick. 26 4 byte pointers by, say 16 characters long just to index 100-200 names?
> Even with a sensible implementation you're going to end up wasting 90% of the storage you
> allocate (and a ten letter name means you have to allocate 1K pointers, each different
> name then requires another 900 bytes or so).
>
There are, of course, more efficient implementations of tries than what
I described above. :) For sparse tries, using a hash table or linked list
to store the child pointers might still be a win. (Aho, Hopcroft, and Ullman's
algorithms book devotes some time to ways of making tries more efficient.)
One big improvement is to not "expand" the tree to the full depth in parts
where there's only one leaf.
> You might have more luck with a binary tree, which just has a 2 way split (or even a
> binary search of a sorted list). The Diku search actually does a linear search, but it
> compares first characters only first. If they match (about 1 in 20) it goes on to
> compare the whole string.
>
Hmm... this seems unnecessary. Wouldn't strcmp() quit as soon as there
was a difference in the strings anyway? You'd only be saving the
function call overhead, which could be eliminated by inlining.
Binary search is certainly going to be good enough in the 100-200 name range.
The nice feature of tries, though, is that search time scales with the length
of names rather than with the number of names. (Similar algorithms have been
proposed--- and I think are currently in use--- for IP routing, where the
number of entries are in the 55-60k prefix range)
If, for example, all 10000+ mobiles in a game had distinct names, there
might be a better case for using a smarter data structure. OTOH, at large
scales, other methods of scaling (like breaking up into regions) start
making sense, too. But even in that case, I think more directory service
support is going to be called for. I'm not trying to explore the benefits
of a specific data structure so much as of making indexes and naming explicit.
Mark Gritter
mgritter@cs.stanford.edu - Naming and Directories? Jon A. Lambert
- Naming and Directories? Hans-Henrik Staerfeldt
- Naming and Directories? Ola Fosheim Grøstad
- Naming and Directories? Mark Gritter
- Naming and Directories? Chris Gray
- Naming and Directories? Caliban Tiresias Darklock
- Naming and Directories? Ben Greear
- Naming and Directories? Mik Clarke
- Naming and Directories? Chris Gray
- Naming and Directories? Chris Gray
- Naming and Directories? Chris Gray
- Naming and Directories? Jo Dillon
- Naming and Directories? J C Lawrence
- Naming and Directories? Mark Gritter
- Naming and Directories? Ola Fosheim Grøstad
- Naming and Directories? Mark Gritter
- Naming and Directories? Ola Fosheim Grøstad
- Naming and Directories? Chris Gray
- Naming and Directories? J C Lawrence
- Naming and Directories? Jo Dillon
- Naming and Directories? Jay Carlson
- Naming and Directories? Jon A. Lambert
- Naming and Directories? Ola Fosheim Grøstad
- Naming and Directories? J C Lawrence
- Naming and Directories? Ola Fosheim Grøstad
- Balancing a Mud Martin C Sweitzer
- Balancing a Mud Neerenberg, AaronX
- Balancing a Mud Mik Clarke
- Balancing a Mud Martin C Sweitzer
- Multiple clients (was How to support 1000+ simultaneous connec Marc Bowden
- ADMIN: Signature length J C Lawrence
- distributed, _untrusted_ servers Oliver Jowett
- OT ADMIN: Web links to MUD-Dev J C Lawrence
- (fwd) MUD Economies J C Lawrence
- (fwd) MUD Economies J C Lawrence
- (fwd) MUD Economies J C Lawrence
- (fwd) MUD Economies J C Lawrence
- Potential New Laws Benjamin D. Wiechel
- Mud Economies (A simple idea) Wes Connell
- Self-organizing worlds (was: Elder Games) B. Scott Boding
- Self-organizing worlds (was: Elder Games) Mik Clarke
- Self-organizing worlds (was: Elder Games) Koster, Raph
- Self-organizing worlds (was: Elder Games) Nicholas Lee
- Self-organizing worlds (was: Elder Games) Koster, Raph
- Self-organizing worlds (was: Elder Games) B. Scott Boding
- Self-organizing worlds (was: Elder Games) Nicholas Lee
- Self-organizing worlds (was: Elder Games) Ola Fosheim Grøstad
- Self-organizing worlds (was: Elder Games) Martin Keegan
- Self-organizing worlds (was: Elder Games) Ola Fosheim Grøstad
- Self-organizing worlds (was: Elder Games) Nicholas Lee
- Mass Creation OLC Functions (idea from Elder Games) Wes Connell
- Mass Creation OLC Functions (idea from Elder Games) Matthew Mihaly
- Mass Creation OLC Functions (idea from Elder Games) Nathan F Yospe
- Mass Creation OLC Functions (idea from Elder Games) Matthew Mihaly
- Mass Creation OLC Functions (idea from Elder Games) Nathan F Yospe
- Mass Creation OLC Functions (idea from Elder Games) Ola Fosheim Grøstad
- Mass Creation OLC Functions (idea from Elder Games) Nathan F Yospe
- Mass Creation OLC Functions (idea from Elder Games) Ola Fosheim Grøstad
- Mass Creation OLC Functions (idea from Elder Games) Brandon A Downey
- Mass Creation OLC Functions (idea from Elder Games) Adam Wiggins
- Mass Creation OLC Functions (idea from Elder Games) Martin C Sweitzer
- Mass Creation OLC Functions (idea from Elder Games) Quzah [softhome]
- Mass Creation OLC Functions (idea from Elder Games) Richard Woolcock
- Mass Creation OLC Functions (idea from Elder Games) Chris Gray
- Mass Creation OLC Functions (idea from Elder Games) J C Lawrence
- Mass Creation OLC Functions (idea from Elder Games) Christopher Allen
- Mass Creation OLC Functions (idea from Elder Games) Matthew Mihaly
- Mass Creation OLC Functions (idea from Elder Games) Chris Gray
- Mass Creation OLC Functions (idea from Elder Games) J C Lawrence
- Mass Creation OLC Functions (idea from Elder Games) J C Lawrence
- On the topic of Mud AI Leif Hardison
- On the topic of Mud AI Nicholas Lee
- On the topic of Mud AI Andrew Norman
- Unicode, ascii and names Ola Fosheim Grøstad
- Variable-sized structures in C (was: Naming and Directories) T. Alexander Popiel
- Variable-sized structures in C (was: Naming and Directories) Ola Fosheim Grøstad
- Renaming objects. John Hopson
- Renaming objects. David Bennett
- Variable-sized structures in C (was: Naming and Directories) Petri Virkkula
- Self-organizing worlds (was: Elder Games) Koster, Raph
- Self-organizing worlds (was: Elder Games) Ola Fosheim Grøstad
- online economy behavior (was: Self-organizing worlds) Robert Green
- online economy behavior (was: Self-organizing worlds) Matthew Mihaly
- online economy behavior (was: Self-organizing worlds) Adam Wiggins
- online economy behavior (was: Self-organizing worlds) Robert Green
- online economy behavior (was: Self-organizing worlds) Matthew Mihaly
- online economy behavior (was: Self-organizing worlds) Matthew Mihaly
- online economy behavior (was: Self-organizing worlds) Christopher Allen
- Self-organizing worlds (was: Elder Games) Koster, Raph
- Self-organizing worlds (was: Elder Games) Koster, Raph
- Self-organizing worlds (was: Elder Games) Chris Gray
- Self-organizing worlds (was: Elder Games) Benjamin D. Wiechel
- Self-organizing worlds (was: Elder Games) Mik Clarke
- online economy behavior (was: Self-organizing worlds) Chris Gray
- OT: just a little something... Ola Fosheim Grøstad
- (fwd) implications J C Lawrence
- Downtime J C Lawrence
- Getting Started with Mud Server Stormblade
- Getting Started with Mud Server Ross Nicoll
- Getting Started with Mud Server Jim Clark
- Getting Started with Mud Server Ben Greear
- Getting Started with Mud Server Chris Gray
- Getting Started with Mud Server Jo Dillon
- Getting Started with Mud Server Hans-Henrik Staerfeldt
- Terms Ola Fosheim Grøstad