Re: Introduction Code, of One Sort or Another

From: Patrick J. Dughi (dughi@IMAXX.NET)
Date: 11/11/97

> people. Running through the list, needless to say, put some serious lag
> into the game.
> Basically what I have been planning is doing both: sorting and a linked
> list. Actually, 26 linked lists. I'll have it check the first letter, then
> have a smaller list based on that.
> Alternatively am thinking of some sort of an array that would basically be
> on/off for the player, but thinking while that would be fast it would be
> horribly memory inefficient.
> Hrmns. Any followups on this thread would be appreciated, just remember
> that you'd want to run a LOT of intros through and then have a lot of
> people all in the same room.

        Maybe if you hashed your data, you'd have an easily increased
lookup time.

        Hashing is easy, and terribly quick.  Here's an example of a
hashing algorithm (poor example).  Lets assume that you've got a small
mud, and chances are that you'll never have one person introduced (or,
more importantly, needing to remember) more than 300 people.  Great.
Create an array sized around 300.  Now, everytime someone introduces
themselves, save the information in the following way:

   take their uid, and divide it by 300 (the size of the array).  Take the
remainder of that, and throw in their actual name.  If that array slot is
already taken, make it an array of linked objects and simply put it on the
next one.

  Example in use:

        Shemp walks into a room with three people in it; Larry, Curly, and
Moe.  Shemp has been introduced to Curly and Moe, but not to Larry.
Upon entering, Moe's uid is hashed using the above alogrithm, and the slot
is checked.  Say Moe is the only one in the slot - the algorithm says
"Yes, we know Moe.".  Then, Curly - however, lets say Curly isn't the only
one in that slot.. what do we do?  We walk down the list in the slot till
we find a Curly's name, great, now we know we know Curly too. Now, we hash
Shemp, look at the slot, but its empty - or maybe it has someone in it,
but they're not Shemp - get to the end, and still no Shemp, so, we don't
know him.  For three people, you get maybe 5-6 string comparisons, and
thats it.  Best case, 300 people, 300 string comps, but you'll probably
average more around 1000+ in this case, because its not a very good hash
function, though it is easy.  Sorting is quick too, so its not very

               I'm sure you could come up with a better hash function in
your sleep.


     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     | |

This archive was generated by hypermail 2b30 : 12/08/00 PST