4 ms·
Tries are great for caching URLs & other path-like data. I've found them to be faster (and smaller) than hashes for these purposes in the past. However, this w
by sambeau 13y ago
Tries are great for caching URLs & other path-like data. I've found them to be faster (and smaller) than hashes for these purposes in the past.
However, this was back in the days of tiny caches. I suspect they may have lost the edge they had in 2003.
- sspiff 13y agoThis contradicts chatman's comment at the top, who claims a trie has poor locality. Since you have some experience with tries, do you have an explanation on how to implement tries with good locality properties?
- sambeau 13y agoI'd take his word for it as my tests are 10 years old! And my apologies - looking back it was Patricia trees I was using as you can take a pointer to a mid-point in the path: useful for disk caches etc. I was using them for small dictionaries (mainly symbol table-size structures) comparing them against an early super-fast hash (and I recall for really small dictionaries linear search as I naively assumed that a linear search would win for tiny dictionaries - it didn't). In all my tests then (as I say, 2003, on a 3 year old IBM Thinkpad) the tries won.
- deleted 13y ago[deleted]