7 ms·

It's quite possibly the case that it takes longer to parse the complex trie regex (using character classes, ?, etc.) constructed here than it does for a good re

It's quite possibly the case that it takes longer to parse the complex trie regex (using character classes, ?, etc.) constructed here than it does for a good regexp library to parse the alternating fixed strings and construct the equivalent automata.

roryokane 13y ago
I don’t know how common such “good regexp libraries” are. The README includes a benchmark at the bottom, demonstrating that the complex regex is about ten times faster than the simple version. The benchmark uses Clojure’s built-in regex engine, which is the same as Java’s.
- eru 13y ago
  grep is one example of a programme with a good regex library. Compare http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html
- FreakLegion 13y ago
  Well, PCRE, the most widely used regex lib in my experience, has a "DFA" mode (scare quotes because it's actually an NFA mode. See [1]). So the option is there, even if most people use PCRE in standard recursive kablooey mode. I was working on a drop-in managed wrapper around re2[2] so .NET developers would have access to a good regex library, but damned if starting a company hasn't gotten in the way of finishing it. Still, re2 bindings are available for most other common platforms. (Also I don't believe Java's regex engine is automata-based, which would explain the performance gains.) 1. http://fanf.livejournal.com/37166.html http://fanf.livejournal.com/37166.html 2. http://code.google.com/p/re2/ http://code.google.com/p/re2/
danieldk 13y ago
Especially considering that there are incremental algorithms for constructing the minimized DFA. For instance, I use one such algorithm in my library that (among other things) uses a minimized DFA to store String sets in Java: https://github.com/danieldk/dictomaton https://github.com/danieldk/dictomaton (It also supports perfect hashing automata and Levenshtein automata.)

roryokane 13y ago

I don’t know how common such “good regexp libraries” are. The README includes a benchmark at the bottom, demonstrating that the complex regex is about ten times faster than the simple version. The benchmark uses Clojure’s built-in regex engine, which is the same as Java’s.

eru 13y ago
grep is one example of a programme with a good regex library. Compare http://swtch.com/~rsc/regexp/regexp1.html http://swtch.com/~rsc/regexp/regexp1.html
FreakLegion 13y ago
Well, PCRE, the most widely used regex lib in my experience, has a "DFA" mode (scare quotes because it's actually an NFA mode. See [1]). So the option is there, even if most people use PCRE in standard recursive kablooey mode. I was working on a drop-in managed wrapper around re2[2] so .NET developers would have access to a good regex library, but damned if starting a company hasn't gotten in the way of finishing it. Still, re2 bindings are available for most other common platforms. (Also I don't believe Java's regex engine is automata-based, which would explain the performance gains.) 1. http://fanf.livejournal.com/37166.html http://fanf.livejournal.com/37166.html 2. http://code.google.com/p/re2/ http://code.google.com/p/re2/

danieldk 13y ago

Especially considering that there are incremental algorithms for constructing the minimized DFA. For instance, I use one such algorithm in my library that (among other things) uses a minimized DFA to store String sets in Java: https://github.com/danieldk/dictomaton https://github.com/danieldk/dictomaton (It also supports perfect hashing automata and Levenshtein automata.)