4 ms·

Someone's Marketing team forced them to write an article! But yes, tries are very cool.

• 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 ago
    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
    • taeric 6y ago
      My 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.
• YuukiRey 6y ago
  This made me laugh :D 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.