Re: Grace and Maps (was Re: Development process in the Ada community)

[Ole-Hjalmar Kristensen <oleh@vlinux.voxelvision.no>]

Darren New <dnew@san.rr.com> writes:

> Jeffrey Carter wrote:
> > Maybe my memory is faulty, but I seem to recall that these trees still
> > need rebalancing to maintain O(log N) search times.
> 
> Yes, but only on inserts, only rebalancing of a limited amount of the
> tree (O(log N) for the worst case rebalance) and generally do *not*
> require rebalances on every insert. It's not like keeping a list sorted,
> for example. For example, a red-black tree touches at worse the nodes
> between the node you just inserted and the root, IIRC. A B-tree (which
> is based on blocks of pointers) touches the block you inserted in and
> potentially back to the root, either splitting or combining as needed. 
> 
> Red/black trees don't get nodes moved when they're rebalanced. You just
> adjust the pointers. 
> 

Yes, they are very nice.

> I'm not sure why a hashtable wouldn't have a worst-case time of O(N) (if
> all the elements hash to the same value) or how you'd guarantee any
> particular limit on execution time of inserting a value (for example, in
> the same case). In contrast, a red-black tree is *never* going to see
> O(N) time in any operation.
> 

You're right, you cannot in general guarantee it. But if you use hash
functions which on average change half the bits as a result of a
single bit change in the input, you can rest assured that it will not
happen in practice. A more serious problem is that the average time
increases as you add more data items. For your typical hash link
table, you should try to keep the table not more than 50-80%
full. This will give you search times very close to O(1) with a good
hash function.

For general use, I would certainly prefer a good tree implementation,
but when you need the utmost speed and have a fixed size data set, I
would go for the hash table.

> -- > Darren New > San Diego, CA, USA
> (PST). Cryptokeys on demand.  > The 90/10 rule of toothpaste: the last
> 10% of > the tube lasts as long as the first 90%.