I'll admit I skipped straight to the conclusion after a few demos. How is knowing a "tries" count going to help me beyond knowing "nothing can be sorted faster than n(log(n))"? Every "try" is a retrieval and costs read time?
EDIT: I'm much worse at algorithms than I originally thought.
Ah, well then I'm too drunk to be reading this. Never heard of "tries", guess I haven't read enough. Conclusion could have used some improvement for sure.
Yeah, rereading this article today it really doesn't give a summary of what "tries" are until pretty deep into it. Smiling that the author updated the title because of my debauchery last night.
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.
> 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'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.
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 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?
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.
Skimming the benchmark, I didn't see any negative tests (checking for words not contained), which can be as or more important than the positive case depending on the expected use.
18 comments
[ 5.1 ms ] story [ 53.8 ms ] threadEDIT: I'm much worse at algorithms than I originally thought.
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.
e.g. see https://vincent.bernat.im/en/blog/2017-ipv4-route-lookup-lin...
Later TCAMs came along for hardware lookups.