[Home] [Groups] - Message: [Prev in Group] [Next in Group]

nu.kanga.list.mud-dev

9805: Re: [MUD-Dev] Naming and Directories?

[Full Header] [Plain Text]
From: Mik Clarke <mikclrk@ibm.net>
Newsgroups: nu.kanga.list.mud-dev
Date: Tue, 16 Mar 1999 21:27:44 +0000
References: [1]
Organization: Kanga.Nu
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).

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.

Mik



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