[MUD-Dev] Naming and Directories?
Nathan F Yospe
yospe at hawaii.edu
Sun Mar 14 09:36:44 New Zealand Daylight Time 1999
On Sat, 13 Mar 1999, Mark Gritter wrote:
:Mik Clarke writes:
: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
:I should write up a DevMUD module. :)
I had such a critter in one of the earliest Physmud incarnations. It was
considerably slower (by a third) than a tight hash table for the purpose
of looking up words. My implementation was similar, except that I had an
extra level of switching when the wordbag got small... a bag that was at
least seven links full had the 26 branches, but the smaller ones had the
optimization of holding no empty links, and rapid-checking the links. In
testing, I'd found this became faster than the array-indexing at smaller
sizes, for some reason. I still haven't a clue as to why this would come
to be... in any case, the effective result was a set of objects each the
size of twenty-eight pointers (26 letters, one word-object, one parent),
plus function pointers... not too good, but not that bad... unless, as I
later surmised, it couldn't actually keep *that* close to the CPU, which
it was quite capable of with both the small bags and the hash table. The
truth is, YMMV, and I wish your attempts well.
Nathan F. Yospe - Born in the year of the tiger, riding it forever after
University of Hawaii at Manoa, Dept of Physics, second year senior (joy)
(On Call) Associate Algorithm Developer, Textron Systems Corp, Maui Ops.
yospe#hawaii.edu http://www2.hawaii.edu/~yospe Non commercial email only
MUD-Dev maillist - MUD-Dev at kanga.nu
More information about the MUD-Dev