[MUD-Dev] Naming and Directories?

[Jon A. Lambert]

On 16 Mar 99, Mik Clarke wrote:
> Mark Gritter wrote:
> > Mik Clarke writes:
> > > Given a task of sending a message to a specific player, when that player could be
> > > located anywhere within the mud, how do you propose to do it faster than by running
> > > the list of all connected players?  Sure, a binary index by name might help, but I
> > > suspect you'd have trouble seeing the saving...
> >
> > 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).

But you have changed your requirements above from speed to memory. 
No fair. ;)

The alphabet trie above has some pros and cons:

1) avoids the overhead of string hashing 
2) provides intrinsic support for abbreviations

1) based on English and may not support blanks, puntuation, or other 
characters   (of course this can be altered or enforced)
2) distribution of names may tend to cluster in certain nodes 

> 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.

One could implement a simple hash table (or vector) to divide the link list.  
The hash algorithm would treat the name string as either a 2 byte or 4 byte 
unsigned int which should be cheaper to hash than the entire string.  Of 
course, you would have to enforce a mininum name length.  And it would also 
give you a corresponding mininum abbreviation support. 

--
--*     Jon A. Lambert - TychoMUD       Email:jlsysinc at .ix.netcom.com      *--
--*     Mud Server Developer's Page <http://pw1.netcom.com/~jlsysinc>      *--
--* I am the Dragon of Grindly Grund, but my lunches aren't very much fun, *--
--* For I like my damsels medium rare, And they always come out well done. *--


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