Re: Just wondering, anyone as insane as Hades?

From: Mark Devlin (markd@eskimo.com)
Date: 04/10/96


On Wed, 10 Apr 1996, Michael Buselli wrote:

>      Oh I see what you've done... okay, you beat me on speed there...
> a hash table is an array of linked lists. Say I want to index room
> 1031 and

>      Only thing I disagree with your system is that if you get to the
> point where you start having huge numbers for your vnumbers, your
> array size will be really big.

Another interesting idea would be to use a splay tree.

Splay trees are basically your garden variety binary tree, but
they're self-modifying.

(from memory here) Each time your 'find node' function is successful, it
moves the node to the head of the tree, and reorganizes a few pointers.
This makes frequently used nodes very fast to find, and also tends to
balance out the tree over time.

It's simpler than the hash table, uses only as much space as you need
for the nodes, and is just a little slower in actual use.

However, once the hash table routines are written, it doesn't really
matter. The extra space required by the hash table isn't that bad
either. Just wanted to point out another alternative.

- Mark
markd@eskimo.com	(finger markd@eskimo.com for my PGP signature)



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