5 ms·
So tries are a really cool data structure and they're the natural fit for an autocomplete, but a while back I had to implement an autocomplete widget (over stoc
by nostrademons 11y ago
So tries are a really cool data structure and they're the natural fit for an autocomplete, but a while back I had to implement an autocomplete widget (over stock tickers) and it turns out that for many relatively small, dense data-sets, binary search over a sorted array with a linear scan to find suffixes is a much (10x+) faster approach.
The problem is that a trie is a very cache-loose data structure. Every node is connected to every other by pointers, and they may be spread all over main memory. Finding the first node usually involves chasing several pointers; enumerating each successive one involves chasing several more. Meanwhile, if you just had a sorted array, all subsequent results would be on the same page at least, and many would be on the same cache line.
YMMV, based on your data's size and shape. Sorted arrays usually work best when the full data set is small and dense (eg. stock tickers), while tries may work better for sparse data (eg. sentences typed in by users). Always benchmark before committing to an implementation.
- rch 11y agoYour conclusion is likely correct given your data, but did you happen to evaluate HAT-tries as well? http://crpit.com/confpapers/CRPITV62Askitis.pdf http://crpit.com/confpapers/CRPITV62Askitis.pdf
- nostrademons 11y agoNope I didn't - I did this work in 2006, and the HAT trie didn't come out until 2007. I did try a number of different variations on how to do the internal storage of nodes though - the fastest was what the paper described as a burst-trie - as well as other binary search tree structures. The speed difference was well over 5x though (IIRC, it was something like 17x from best string trie vs. binary search), so if the paper's conclusions hold it probably wouldn't have mattered.
- srean 11y agoYour comment provoked a quick search on pointer-less encoding of tries. It turns out one such implementation was patented in 2006 http://www.google.com/patents/US20060020638 http://www.google.com/patents/US20060020638
- amelius 11y agoAnother problem is that tries are not stored as such in typical databases. You'd have to roll your own database system to support this.
- nostrademons 11y agoIf you're doing an autocomplete widget, you probably want to store all of your data in RAM rather than in any DB. Autocomplete queries fire on every keystroke from every user, so if you hit the DB at all, you've probably killed your server.
- amelius 11y agoWell, I guess the DB already has caching logic to keep things in memory. Or otherwise, it is not such a good DB system.
- nostrademons 11y agoMost have some sort of caching logic but you can't rely on it to do what you want. Always benchmark, and never assume that just because you're paying for something or that it's the industry standard, it does what you want. I've seen a number of devs completely surprised by the throughput & latency numbers they get from their databases because they assume everything is going to be cached in RAM and the database is really hitting disk for some obscure reason on every query.
- amelius 11y agoThis is all really hypothetical. Show me a DB that can do tries first.
- tokenrove 11y agoPostgres with SP-GiST, for example
- jessaustin 11y ago
- mdibaiee 11y agoHey, thanks for pointing these out, appreciated. I'm not aiming for speed in this tutorial, it's just a tutorial to teach how Tries work, I knew arrays are faster in this kind of situation, even an array.filter can do the job, so you're right; but Tries are more flexible in my opinion, they can easily be customized for any use. Anyway, I always like it when I get criticized, I learn something, thank you nostrademons!
- repsilat 11y agoThere's no reason you have to scatter a trre all over the place. Dictionaries almost never change, so you can flatten the pointer data (and maybe even inline the words if you're a masochist) without worrying.