Ternary search trees added to TODO

[Russ Allbery]

Andrew McNamara <andrewm at connect.com.au> writes:

>> That's not clear; I'd like to at least try it.  A lookup in a hash
>> table is linear in the length of the key, so it's O(k) vs. O(lg n + k),
>> which makes the performance difference a little harder to judge.  Plus
>> unsuccessful lookup is frequently much faster, and the operation at
>> each character of the key can be quite a bit faster; it depends on
>> whether pointer chasing is faster than the mathematical operations the
>> hash function is performing.

> The pointer chasing could easily be more expensive than the hash
> function as it will touch more cache lines, potentially faulting in more
> pages (the locality of reference is considerably worse).

True.

(The other place where TSTs may come in handy is with the configuration
file parsing stuff; in that case, there will be a *lot* of failed lookups
in the common case, and more configuration parameters distinguish by the
first few characters than newsgroup names.)

> Since we're on the subject, have you considered splay trees?

No, feel free to plug them!  I'm not being as proactive about seeking out
new data structures as I should be and therefore tend to only hear about
the relative merits of them if they come up on mailing lists I follow.

-- 
Russ Allbery (rra at stanford.edu)             <http://www.eyrie.org/~eagle/>