2 ms·
I fully agree, and yet I have so rarely had direct need for then that it is kind of scary when I see folks reach for them. Worse, they are stupid common in int
by taeric 6y ago
I fully agree, and yet I have so rarely had direct need for then that it is kind of scary when I see folks reach for them.
Worse, they are stupid common in interviews.
- int3 6y agoAs 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
- taeric 6y agoMy problem with them is mainly that constructing them is not trivial. 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.