Regexes: The Bad, the Better, and the Best(loggly.com)
loggly.com
Regexes: The Bad, the Better, and the Best
https://www.loggly.com/blog/regexes-the-bad-better-best/
36 comments
and [0-9] is more specific than \d
"In most flavors that support Unicode, \d includes all digits from all scripts." [1]
EDIT: But I guess for the majority of use cases it doesn't matter [2] since PCRE is the norm almost everywhere.
[1] http://www.regular-expressions.info/shorthand.html
[2] "Notable exceptions are Java, JavaScript, and PCRE. These Unicode flavors match only ASCII digits with \d"
"In most flavors that support Unicode, \d includes all digits from all scripts." [1]
EDIT: But I guess for the majority of use cases it doesn't matter [2] since PCRE is the norm almost everywhere.
[1] http://www.regular-expressions.info/shorthand.html
[2] "Notable exceptions are Java, JavaScript, and PCRE. These Unicode flavors match only ASCII digits with \d"
In many environments,
[0-9]{3}-?[0-9]{4}
taking it to the next level:
[0-9][0-9][0-9]-?[0-9][0-9][0-9][0-9]
[0-9][0-9][0-9]-?[0-9][0-9][0-9][0-9]
This is just another statement of precision vs. recall.
https://en.wikipedia.org/wiki/Precision_and_recall
https://en.wikipedia.org/wiki/Precision_and_recall
Where "Best" = "Most performant". Of course, there's other ways to judge a regex - readability, specificity, robustness...
In most places I used regexes, efficiency is the least of my concerns, though for a company whose product is focused around parsing massive amounts of logs, focusing on performance does make sense.
In most places I used regexes, efficiency is the least of my concerns, though for a company whose product is focused around parsing massive amounts of logs, focusing on performance does make sense.
The RegexBuddy author has a good article on this same phenomenon, dubbed "catastrophic backtracking": http://www.regular-expressions.info/catastrophic.html
How would the regex below compare in this case? That is, modifying the "bad" regex to use the lazy-consumption trick on (almost) all of the `.` patterns.
/.*? (.*?)\[(.*?)\]:.*/Okay but think:
If you are searching a very large file for a very few occurrences of the expected match then this optimization is not so bad.
If you are running line-by-line through a very large log file to extract just those two pieces of information per line, then throw away the first N characters in each line (where N is the hopefully-constant length of your timestamps plus that space char) and start the regex engine at the beginning of the expected match. Then it doesn't have to waste any time passing over those chars.
Even if the exact details above aren't quite right the principal is (and is well-known): Avoid premature optimization! (And the corollary: Measure it. Profile your code, don't guess, you're probably wrong.)
If you are searching a very large file for a very few occurrences of the expected match then this optimization is not so bad.
If you are running line-by-line through a very large log file to extract just those two pieces of information per line, then throw away the first N characters in each line (where N is the hopefully-constant length of your timestamps plus that space char) and start the regex engine at the beginning of the expected match. Then it doesn't have to waste any time passing over those chars.
Even if the exact details above aren't quite right the principal is (and is well-known): Avoid premature optimization! (And the corollary: Measure it. Profile your code, don't guess, you're probably wrong.)
"Awk and grep use the Thompson NFA algorithm which is in fact significantly faster in almost every way but supports a more limited set of features."
AFAIK the only feature of regexes that require backtracking are back-references, as long as your regex doesn't use it why doesn't PCRE switch to the more efficient algorithm, and use the backtracking algorithm only if you actually need the feature that requires backtracking?
AFAIK the only feature of regexes that require backtracking are back-references, as long as your regex doesn't use it why doesn't PCRE switch to the more efficient algorithm, and use the backtracking algorithm only if you actually need the feature that requires backtracking?
Backtracking is required in a lot of cases. Consider matching the pattern /^(AA|AB)*$/ against the string "AAAAAAAAB". Before it can come up with the answer (it doesn't match) the engine has to backtrack all the way from right to left.
that can be compiled to a state machine where a decision to switch states is taken based on current character only, and when all input is consumed you are either in an accepting or rejecting state. In your case I think it only needs 2 states: state 0 moves to state 1 when it sees an A, and state 1 moves to state 0 when it sees either A or B.
For your string it'll be in state 0 when it sees a B and thus rejects it.
┌┐
↓│
┌────┴┐
┌─→│ │←──┐
│ └─────┘ │
╔════╧═╗ ┌──┴──┐
├─→║ ╟───A──→│ │
╚══════╝ └─┬───┘
↑ │
└─────A,B────┘
Backtracking is definitely not required, nor helpful.
That diagram is quite pretty, did you just hand code it?
Not true. Finite automata (NFAs, DFAs) can match that pattern (and any pattern that doesn't involve backreferences or lookaround) in O(n) time where n is the size of the input string. DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression, but this is far better in most cases than the exponential worst-case time in terms of the input string offered by backtracking implementations.
See https://swtch.com/~rsc/regexp/ for information on finite-state-machine implementations of regexp matching.
See https://swtch.com/~rsc/regexp/ for information on finite-state-machine implementations of regexp matching.
> DFA implementations are worst-case O(n ^ 2) in the number of states of the regular expression
What? Why is that? If the NFA has n states, then the DFA in principle might need one state for every possible set of states the NFA might be in, of which there are 2^n. Where does n^2 come from?
What? Why is that? If the NFA has n states, then the DFA in principle might need one state for every possible set of states the NFA might be in, of which there are 2^n. Where does n^2 come from?
My mistake, I meant O(2 ^ n) indeed. Regardless, having exponential time complexity in terms of the regular expression (which is usually controlled by the programmer) where the processing is done at compile-time is much better than having exponential complexity in terms of the input string (which often comes from an untrusted source) where the processing is done at run-time.
Using this Perl module you can walk step-by-step through what a regexp engine actually does given a regexp and a string to match against:
https://metacpan.org/pod/Regexp::Debugger
After installing the module it can be started simply by calling `rxrx` on the command line.
https://metacpan.org/pod/Regexp::Debugger
After installing the module it can be started simply by calling `rxrx` on the command line.
Surely the simplest optimisation to add would be anchors? Instead of starting the 'good' line "[12]", start it "^[12]".
As it stands, the 'good' regex will look through the whole line for any occurrence of 1 or 2 in the line, then start applying the rest of the regex from there. Putting an anchor in means it only looks at the first character for that 1 or 2.
As it stands, the 'good' regex will look through the whole line for any occurrence of 1 or 2 in the line, then start applying the rest of the regex from there. Putting an anchor in means it only looks at the first character for that 1 or 2.
Inspiring post - I'll be sure to put extra thought into how I write my regexes from here on out.
Does anyone know a good browser-based game that trains you to do regexes well?
Does anyone know a good browser-based game that trains you to do regexes well?
Bug in the month matching, instead of [01]\d which will also match 13-19, maybe try something like: (0[1-9]|[1-9]|1[0-2]) https://goo.gl/RMv4x2
gesman(1)
[deleted]
I'd rather word this as "more specific is better". Like say for a U.S. phone number (minus area code for simplicity),
is better than
because it's more specific.
"Longer is better" is only useful for helping identify which regex is better, not for helping write better regexes.