6 ms·

Trees, Hash Tables and Tries

32 points by skorks 17y ago

timtadh 17y ago
I have also been getting into tries recently (last 6 months) and if you are interested in learning about them I recommend Sedgewick's Algorithms in C (parts 1-4) for a good introduction to the subject. Available on Safari if you have access to that.
liuliu 17y ago
I will argue that a properly implemented tries are more compact but not necessarily faster than hash table. The fact is, there are some badly implemented tries which even worse than hash table in term of memory consumption. Also, I'd like to point out the actually trie implementation may not have a fix k child node. I most often use k = 256 or 512 for the first few layers and 4~8 for the last few one in order to get "hash table" like performance for the first few layers and "tree" like performance for a deeper lookup.
- mhansen 17y ago
  I will argue that a properly implemented tries are more compact but not necessarily faster than hash table. Where do you argue this? The fact is, there are some badly implemented tries which even worse than hash table in term of memory consumption. Any data structure can be badly implemented. What use is comparing a badly implemented data structure to a well-implemented one?
  - liuliu 17y ago
    It seems in the article the author suggests that in certain case tries is faster than hash table. Yes, you are right about every data structure can be badly implemented. But some data structures are more easily to get wrong. For example, everyone have no problem with selection sort, it is just hard to get it wrong. But for binary search, some decent programmer may write (a + b) / 2. Same case for tries, people more commonly (intuitively) write things like node_t* child[26];
AlisdairO 17y ago
In the real world, it's unlikely that a trie of any real size will be comparably performant to a hash table with a sane hash function: trie algorithms involve moving from node to node, each of which will require an unpredictable retrieval from non-sequential memory. Memory latency is pretty high these days (~200 cycles), so hash tables will almost always be quicker. This is not to say that radix tries aren't extremely useful - they're compact and fast - but they're unlikely to match a hash table for raw performance.
- jules 17y ago
  Here's an interesting paper. It describes a cross between a trie and a hash table. Instead of storing the string itself in the trie, it first hashes the string and then stores that in a trie (in a smart way). The memory usage is claimed to be very good, and the benchmarks in the paper seem to show that it's faster than a hash table for lookup... http://lampwww.epfl.ch/papers/idealhashtrees.pdf http://lampwww.epfl.ch/papers/idealhashtrees.pdf
  - AlisdairO 17y ago
    Thanks for the link! I'll be interested to take a look.
  - angstrom 17y ago
    Another good example that can be more performant than a hash or a trie on a given alphabet is a directed acyclic word graph. Think of it as a trie that reuses edges, but has no cycles. This makes it very compact. There's an implementation of one here that I've messed with, but it's a little expensive on the setup side. http://www.pathcom.com/~vadco/dawg.html http://www.pathcom.com/~vadco/dawg.html The final result is that each node is stored in a 32bit word with the possible characters limited to a 5 bit field. 1 bit flag for word endings and I believe he employed offsets with the rest of the bits to perform the directed lookups of the other characters in a limited A-Z uppercase only alphabet. These types of graphs tend to extremely fast at runtime, but like I mentioned, the setup is costly. However, if you were embedding this in a device this would definitely be a worthwhile investigation. This is one of those cases where a data structure fits a very constrained, but well defined requirement.
senderista 17y ago
In the same way, any naively "constant space" algorithm that indexes into an array with a fixed number of pointers or indices is technically O(log n) in space, since you need log n bits to index n objects. So a space factor of log n can generally be treated as constant in practice.

32 points by skorks 17y ago

I have also been getting into tries recently (last 6 months) and if you are interested in learning about them I recommend Sedgewick's Algorithms in C (parts 1-4) for a good introduction to the subject. Available on Safari if you have access to that.

liuliu 17y ago

I will argue that a properly implemented tries are more compact but not necessarily faster than hash table. The fact is, there are some badly implemented tries which even worse than hash table in term of memory consumption. Also, I'd like to point out the actually trie implementation may not have a fix k child node. I most often use k = 256 or 512 for the first few layers and 4~8 for the last few one in order to get "hash table" like performance for the first few layers and "tree" like performance for a deeper lookup.

mhansen 17y ago
I will argue that a properly implemented tries are more compact but not necessarily faster than hash table. Where do you argue this? The fact is, there are some badly implemented tries which even worse than hash table in term of memory consumption. Any data structure can be badly implemented. What use is comparing a badly implemented data structure to a well-implemented one?
- liuliu 17y ago
  It seems in the article the author suggests that in certain case tries is faster than hash table. Yes, you are right about every data structure can be badly implemented. But some data structures are more easily to get wrong. For example, everyone have no problem with selection sort, it is just hard to get it wrong. But for binary search, some decent programmer may write (a + b) / 2. Same case for tries, people more commonly (intuitively) write things like node_t* child[26];

AlisdairO 17y ago

In the real world, it's unlikely that a trie of any real size will be comparably performant to a hash table with a sane hash function: trie algorithms involve moving from node to node, each of which will require an unpredictable retrieval from non-sequential memory. Memory latency is pretty high these days (~200 cycles), so hash tables will almost always be quicker. This is not to say that radix tries aren't extremely useful - they're compact and fast - but they're unlikely to match a hash table for raw performance.

jules 17y ago
Here's an interesting paper. It describes a cross between a trie and a hash table. Instead of storing the string itself in the trie, it first hashes the string and then stores that in a trie (in a smart way). The memory usage is claimed to be very good, and the benchmarks in the paper seem to show that it's faster than a hash table for lookup... http://lampwww.epfl.ch/papers/idealhashtrees.pdf http://lampwww.epfl.ch/papers/idealhashtrees.pdf
- AlisdairO 17y ago
  Thanks for the link! I'll be interested to take a look.
- angstrom 17y ago
  Another good example that can be more performant than a hash or a trie on a given alphabet is a directed acyclic word graph. Think of it as a trie that reuses edges, but has no cycles. This makes it very compact. There's an implementation of one here that I've messed with, but it's a little expensive on the setup side. http://www.pathcom.com/~vadco/dawg.html http://www.pathcom.com/~vadco/dawg.html The final result is that each node is stored in a 32bit word with the possible characters limited to a 5 bit field. 1 bit flag for word endings and I believe he employed offsets with the rest of the bits to perform the directed lookups of the other characters in a limited A-Z uppercase only alphabet. These types of graphs tend to extremely fast at runtime, but like I mentioned, the setup is costly. However, if you were embedding this in a device this would definitely be a worthwhile investigation. This is one of those cases where a data structure fits a very constrained, but well defined requirement.

senderista 17y ago

In the same way, any naively "constant space" algorithm that indexes into an array with a fixed number of pointers or indices is technically O(log n) in space, since you need log n bits to index n objects. So a space factor of log n can generally be treated as constant in practice.