News for hackers. Stuff that matters.
Re:The Trie: A Neglected Data Structure by sspiff on Friday September 13, 2013 @11:20AM (#6381038)
This 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?
Re:The Trie: A Neglected Data Structure by sambeau on Friday September 13, 2013 @11:35AM (#6381127)
I'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.