As an interviewer who likes asking about them... I'd say they're surprisingly useful.
- Barring very degenerate inputs, prefix tries are usually faster than `std::set<std::string>`. And for longer strings, prefix tries are definitely faster than `std::unordered_set<std::string>`.
- The same ideas that apply to strings apply to bitvectors too, so we can handle arbitrary binary data the same way. (This gives us things like Patricia trees.)
- They're great for implementing immutable sets. In fact most functional languages use some variant of prefix tries for their set/map data structures.
And some real-world use cases:
- Symbol lookup in mach-O (macOS) binaries use prefix tries
- One of the fastest string sorting algorithms (burstsort) uses prefix tries
- Program analysis / abstract interpretation really benefits from immutable sets of bitvectors with fast union operations
- Pretty sure every typeahead / autocomplete implementation uses some kind of trie
- And for something a bit more esoteric: scrabble/boggle AIs use them too
I want to point out that I wasn't forced though. Rather, they asked around if people have some interesting things to share and this particular PR seemed a good fit for an article. I don't really write about Go stuff on my own blog so I figured why not contribute to our company blog.
Thanks for writing this up. I'm solving a similar problem, albeit different in a few important ways, and was planning on taking a semi-similar approach. Like you, today I'm using a fairly naive implementation with some less-than-ideal complexity.
I've never actually worked with a prefix tree before, so this was quite helpful for me.
This may be of interest as well - a related paper, Pigasus, does this with specialized hardware but it's a similar problem of applying 10s of thousands of rules as quickly as possible. I found it while reading through acolyer's morning paper.
https://blog.acolyer.org/2020/11/16/pigasus/
Again, slightly different task - they wouldn't be going for the longest match exclusively, but all matches. Also, the rules they use are fundamentally regular expressions, so the filtering pass is to take advantage of the domain specific knowledge that rule-matches are very rare.
My guess is your "fundamentally regular expressions" is, in fact "fundamentally an automata". Which, my guess is even this article could have used an automata such that they are basically lexing the data they are using over.
I assume you're saying that the regular expressions used are likely to be equivalent to a DFA? If so, I agree, that's very likely, and I was also thinking about that.
I believe Go's regex engine is built on RE2 though, so idk.
Essentially, yes. My point is if you implemented the dfa directly, then you could just iterate all the characters doing whatever the current state of the automata says to do at each character.
> Because of that, the first step on the road to fast programs is to measure!
> Making an operation that accounts for 1% of the overall runtime 100% faster is far less effective than making something that accounts for 50% of the runtime10% faster.
Currently dealing with a slow DB and a team of "engineers" who have just NOT internalized the above. It's been very demoralizing.
If someone can implement a code analyzer that could suggest such optimizations we could save so many compute cycles. Using tries for such problems is a common solution but may be unknown or overlooked by some. Even trying to search for best practices to a problem you feel has likely been solved many times before can be difficult if you don't use the right keywords.
13 comments
[ 3.3 ms ] story [ 39.7 ms ] threadBut yes, tries are very cool.
Worse, they are stupid common in interviews.
- Barring very degenerate inputs, prefix tries are usually faster than `std::set<std::string>`. And for longer strings, prefix tries are definitely faster than `std::unordered_set<std::string>`.
- The same ideas that apply to strings apply to bitvectors too, so we can handle arbitrary binary data the same way. (This gives us things like Patricia trees.)
- They're great for implementing immutable sets. In fact most functional languages use some variant of prefix tries for their set/map data structures.
And some real-world use cases:
- Symbol lookup in mach-O (macOS) binaries use prefix tries
- One of the fastest string sorting algorithms (burstsort) uses prefix tries
- Program analysis / abstract interpretation really benefits from immutable sets of bitvectors with fast union operations
- Pretty sure every typeahead / autocomplete implementation uses some kind of trie
- And for something a bit more esoteric: scrabble/boggle AIs use them too
I suspect you are right on most uses, though for many first iterations a simple ordered set works wonderfully well, and is much easier to think of.
I want to point out that I wasn't forced though. Rather, they asked around if people have some interesting things to share and this particular PR seemed a good fit for an article. I don't really write about Go stuff on my own blog so I figured why not contribute to our company blog.
I've never actually worked with a prefix tree before, so this was quite helpful for me.
This may be of interest as well - a related paper, Pigasus, does this with specialized hardware but it's a similar problem of applying 10s of thousands of rules as quickly as possible. I found it while reading through acolyer's morning paper. https://blog.acolyer.org/2020/11/16/pigasus/
Again, slightly different task - they wouldn't be going for the longest match exclusively, but all matches. Also, the rules they use are fundamentally regular expressions, so the filtering pass is to take advantage of the domain specific knowledge that rule-matches are very rare.
I believe Go's regex engine is built on RE2 though, so idk.
> Making an operation that accounts for 1% of the overall runtime 100% faster is far less effective than making something that accounts for 50% of the runtime10% faster.
Currently dealing with a slow DB and a team of "engineers" who have just NOT internalized the above. It's been very demoralizing.
https://www.youtube.com/watch?v=r-TLSBdHe1A
And who knows, maybe they'd even be interested in using coz afterwards:
https://github.com/plasma-umass/coz