News for hackers. Stuff that matters.
Re:The Trie: A Neglected Data Structure by chatman on Friday September 13, 2013 @11:16AM (#6381010)
A trie is a poor data structure in practice. There is no locality of reference that can be exploited: to lookup a single key, almost the entire length of the memory blocks occupied by the trie needs to be accessed, and almost at random (depending on the insertion technique). For keys inserted later on, the number of different blocks of memory accesses needed for a single key is proportional to the length of the key.

A B-Tree is better due to better exploitation of locality of reference in memory.

Re:The Trie: A Neglected Data Structure by swannodette on Friday September 13, 2013 @12:22PM (#6381439)
It depends on the kind of trie that you build - it's worth taking a look at Hash Array Mapped Tries http://lampwww.epfl.ch/papers/idealhashtrees.pdf

The Clojure programming language is completely designed around several immutable variants.

Re:The Trie: A Neglected Data Structure by judofyr on Friday September 13, 2013 @11:33AM (#6381115)
See also: HAT-trie by Askitis and Sinha.

Tries are the fastest tree-based data structures for managing strings in-memory, but are space-intensive. The burst-trie is almost as fast but reduces space by collapsing trie-chains into buckets. This is not however, a cache-conscious approach and can lead to poor performance on current processors. In this paper, we introduce the HAT-trie, a cache-conscious trie-based data structure that is formed by carefully combining existing components.