Ternary search trees added to TODO
rra at stanford.edu
Wed May 9 13:05:09 UTC 2001
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).
(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/>
More information about the inn-workers