5 ms·
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
by spadros 8y ago
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.
- 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.
- spadros 8y agoThanks a lot, I'm actually so embarrassed right now. Never confidently log onto Hacker News drunk and expect to contribute in a meaningful way.
- saagarjha 8y agoHi, 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.
- kjeetgill 8y agoI 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?