After reading that, I wonder if trie-s (i.e. judy arrays) would beat hash tables in this exercise... (and I also think that hardcoding the results wasn't cheating)
For the record, and I am sure it's what you meant, a more specific description of Judy arrays is that they are a specific type of trie(though a trie is a specialization of a tree a trie is more rigorous.)
Actually no. That's only a binding if you look at the source code.
The sole C source code is only about 2-3 lines long with a "#include <Judy.h>" which isn't even included while the haskell source is littered with foreign function calls.
With some pointer arithmetic, I would imagine so (with tries, not sure what judy arrays are)... although it might depend into how quickly memory can be allocated/accessed. Assuming the text is a set of lower-case alphabet character strings, you could define a 26-ary trie with very few instructions to do each characters' lookup...
I would be willing to bet that that implementation is slower than a hash table.
(Yeah, I do have some data to back that up - I wrote & benchmarked an autocomplete implementation for a financial software firm. String tries were roughly 10x slower than binary searching an array for a 20k word corpus, which is probably around the size you're dealing with here. They have terrible cache locality - each character makes you follow a pointer, which is probably a cache miss, and the total size of the trie is on the order of 26 * 8 * 20k = 4M. They become a bit better if the number of distinct words in the corpus is small (so that everything fits into cache) or if the number of words is huge (so that your hashtable or array blows the cache anyway).
I've had the opposite experience with Tries v. Hash tables. Though that could be a result of the Trie implementation. Dual array tries have really impressive lookup times, especially compared to the naive implementation... Insertion is pretty bad though. (Though that can be mitigated: http://www.gongcaichun.info/PPT/21.pdf)
The structure of your data matters a lot. If one will fit in cache but the other won't, the one that fits in cache will almost always win. Then they have different big-O characteristics: binary searching an array is O(log N) where N is the number of items, a trie is O(k) where k is the length of the key, a hashtable is O(1), but this is misleading because the hash function is usually O(k) and performance can degrade to O(n) if you have lots of hash collisions.
I thought that an autocompletion widget for stock tickers would be the perfect application for tries: short, dense key space, lots of elements, and a fair likelihood of hash collisions. But apparently not, because our data size just happened to be one where cache effects dominate. I talked to one of the GMail guys later and he was quite surprised, from which I inferred (but it was not stated) that GMail probably uses tries to good effect.
Right on. My point was simply that the type of Trie you use has an effect on the data's size in memory. A dual-array setup is pretty good at keeping the data small... There's very little pointer overhead and proximity is fairly good as well.
