2 ms·
Always a worthy, related mention: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html Another fun idea is the opposite of the
by kqr 4y ago
Always a worthy, related mention: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html
Another fun idea is the opposite of the regex: the regex constructs a state machine of the needle and is then quickly able to run many haystacks through it. Sometimes you need the other optimisation: compile the entire haystack down to a state machine, and you can run many needles through it! It becomes a very primitive search index.
- zwkrt 4y agoThat link is a very high quality write up. I’m having a hard time understanding how your “haystack compilation” would work. I get the desire to be able to efficiently run many regexes on the same large file, but how could you optimize the file for arbitrary regex matching?
- jstrieb 4y agoThe haystack idea reminds me of this wonderful post from the creator of both the Rust regex crate and the ripgrep command line utility (among other awesome things). https://blog.burntsushi.net/transducers/ https://blog.burntsushi.net/transducers/
- metadat 4y agoInteresting read. Also discussed only 1 year ago: https://news.ycombinator.com/item?id=28243636 https://news.ycombinator.com/item?id=28243636 (174 points, 10 comments)
- lagt_t 4y agoJanuary 2007 No thanks
- Cu3PO42 4y agoHow is the age relevant here? The article doesn't deal with current events or the newest hottest framework. It explains algorithms and abstract ideas which haven't changed in the last 15 years.