5 ms·
Tries as the evolution of nothing
- spadros 8y agoI'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.
- bijection 8y agoI think the author means the data structure 'trie', not the action 'try': https://en.wikipedia.org/wiki/Trie https://en.wikipedia.org/wiki/Trie
- spadros 8y agoAh, 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.
- spadros 8y agoYeah, 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.
- CoolGuySteve 8y agoDon'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.
- bjoli 8y agoI 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.
- lamacase 8y agoI think you mean pedantic trie-hard
- spadros 8y agoLaughed pretty hard
- JadeNB 8y ago> 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.
- deleted 8y ago[deleted]
- pedant-triehard 8y agoI'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-linux https://vincent.bernat.im/en/blog/2017-ipv4-route-lookup-lin... Later TCAMs came along for hardware lookups.
- blattimwind 8y agoTries are used by various networking systems in a similar capacity, e.g. both zeromq and nanomsg use tries to match subscription topics in pubsub.
- fshaun 8y agoSkimming 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.