Hacker News new | past | comments | ask | show | jobs | submit login
Tries as the evolution of nothing (wordsandbuttons.online)
50 points by okaleniuk on Aug 7, 2018 | hide | past | web | favorite | 16 comments

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.

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.

I think the author means the data structure 'trie', not the action 'try': https://en.wikipedia.org/wiki/Trie

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.

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.


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

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact