Hacker News Reader

Comment by CoolGuySteve | Hacker News Reader

Don't worry about it, tries are an almost entirely interview question specific data structure.

Of course as soon as you say that, some pedantic try-hard with their real name as their hnews handle will swoop in and tell you that time they saved Google by implementing one in production in under 20 minutes.

View on HN

Hi, it’s me, the pedantic try-hard with my real name as my Hacker News handle, and I’d like to tell you about the time I saved a project by implementing a trie (ok, a finite state machine derived from a trie) to speed up string matching by two orders of magnitude using the Aho-Corasick algorithm.

I'll bite: tries were (and are still?) used for longest prefix match lookups on IP addresses in forwarding plane software and hardware. I've actually seen and worked with tries in real, shipping, working hardware/software.

e.g. see https://vincent.bernat.im/en/blog/2017-ipv4-route-lookup-lin...

Later TCAMs came along for hardware lookups.

Tries are used by various networking systems in a similar capacity, e.g. both zeromq and nanomsg use tries to match subscription topics in pubsub.

I don't think it's too pedantic to mention common non-interview uses. They're pretty core to search and spell checks problems. Or url routes in a webserver. Or routing IPs. Or keywords in a compiler. You know, anytime you have a set of a bunch of strings and you need to find one?

Thanks a lot, I'm actually so embarrassed right now. Never confidently log onto Hacker News drunk and expect to contribute in a meaningful way.

To be fair, the name is pretty terrible! ("Prefix tree" is a much better name for them IMO)

Yeah I smiled this morning when I logged on to do some damage control on this thread and saw that the author updated the title.

I see what you are saying, and I agree somewhat. They have uses that most people won't have to implement themselves though. Many persistent data structure use tries. They have been getting loads of attention, especially since clojure started using them.

> Of course as soon as you say that, some pedantic try-hard with their real name as their hnews handle will swoop in and tell you that time they saved Google by implementing one in production in under 20 minutes.

You say that like it's a bad thing, but isn't it good? If I think that something is of only academic interest, and then I find out about a real-world application, I feel that I have learned something that's worth knowing.

I think you mean pedantic trie-hard

Laughed pretty hard

Reply on news.ycombinator.com