On Tue, 11 Nov 1997, StormeRider wrote:
->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.
So, essentially a hash table that uses linked lists to resolve
collisions? The key is fairly simple (LOWER(*name)-'a') though it
wouldn't be the perfect hash key (the search for which is something
akin to Arthur's quest for the Sangreal) that so many programmers
search for. The approach is simple and fast. The memory usage isn't
exactly costly. Let's say we use 12 bytes for each entry in the
linked list (32-bit integer and the 8 byte next pointer), and everyone
knows 100 people. That's 1.2k per player, and we have 50 players
online [a pretty good amount, especially for MUDs that have "radical"
changes, because most people stick to familiarity], meaning we use a
grand total of 60k to the lists (there's a bit more memory overhead
because of our array). The average number of items in one of the
lists will be ~3.8.
That's pretty speedy, assuming I haven't messed up my math (and it's
possible). No exact figure on how long it'll take you to traverse a
(unsorted, <wink> SB) linked list whose average length is 4, as I
think we can agree the time is insignifgant [Circle traverses much
bigger linked lists very quickly].
daniel koepke / dkoepke@california.com
+------------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
| http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 12/08/00 PST