Menu
I'm not sure I completely understand what is going on with the following regular expression search:
>>> import re
>>> template = re.compile("(\w+)+\.")
>>> target = "a" * 30
>>> template.search(target)
search() call takes minutes to complete, CPU usage goes to 100%. The behavior is reproduceable for both 2.7.5 and 3.3.3 Python versions.
Interesting fact that if the string is less than 20-25 characters in length, search() returns like in no time.
What is happening?
843
My experience shows that most of the time developers focus on correctness of a regex, leaving aside its performance. Yet matching a string with a regex can be surprisingly slow. So slow it can even stop any JS app or take 100% of a server CPU time causing denial of service (DOS).
Regex is faster for large string than an if (perhaps in a for loops) to check if anything matches your requirement. If you are using regex as to match very small text and small pattern and don't do it because the matcher function . find() is slower than a normal if statement of a switch statement.
In General, the Longer Regex Is the Better Regex Good regular expressions are often longer than bad regular expressions because they make use of specific characters/character classes and have more structure. This causes good regular expressions to run faster as they predict their input more accurately.
$ means "Match the end of the string" (the position after the last character in the string). Both are called anchors and ensure that the entire string is matched instead of just a substring.
Understanding this problem requires understanding how NFA works under RegExp.
Elaborating the definition of NFA may be a mission too heavy for me. Search NFA on wiki it will gives you a better explanation. Here just think NFA is a robot finding patterns you give.
Crudely implemented NFA is somewhat dumb, it just looks ahead one or two tokens you give. So in the synthetic example you give, NFA just looks \w+ at first (not parenthesis for grouping).
Because + is a greedy quantifier, that is, matches as many characters as possible, so NFA dumbly continues to consume characters in target. After 30 as, NFA encounters the end of string. After then does NFA realize that he needs to match other tokens in template.
The next token is +. NFA has matched it so it proceeds to \.. This time it fails.
What NFA does next is to step one character back, trying to match the pattern by truncating the submatching of \w+. So NFA split the target in to two groups, 29 as for one \w+, and one trailing a. NFA first tries to consume the trailing a by matching it against the second +, but it still fails when NFA meeting \.. NFA continues the process above until it gets a full match, otherwise it will tries all possible partitions.
So (\w+)+\. instructs NFA to group target in such manner: target is partitioned into one or more groups, at least one character per group, and target is end with a period '.'. As long as the period is not matched. NFA tries all partitions possible. So how many partitions are there? 2^n, the exponential of 2. (JUst think inserting separator between a). Like below
aaaaaaa a
aaaaaa aa
aaaaaa a a
.....
.......
aa a a ... a
a a a a a .... a
If NFA matches \., it won't hurt much. But when it fails to match, this expression is doomed to be never-ending exponential .
I'm not advertising but Mastering Regular Expression is a good book to understand mechanism under RegExp.
138
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
