Why does this take so long to match? Is it a bug?

by

There is some catastrophic backtracking going on that will cause an exponential amount of processing depending on how long the non-match string is. This has to do with your nested repetitions and optional comma (even though some regex engines can determine that this wouldn’t be a match with attempting all of the extraneous repetition). This is solved by optimizing the expression.

The easiest way to accomplish this is to just look for 1+ digits or commas followed by a slash and the end of the string: [\d,]+/$. However, that is not perfect since it would allow for something like ,123,,4,5/.

For this you can use a slightly optimized version of your initial try: (?:\d,?)+/$. First, I made your repeating group non-capturing ((?:...)) which isn’t necessary but it provides for a “cleaner match”. Next, and the only crucial step, I stopped repeating the \d inside of the group since the group is already repeating. Finally, I removed the unnecessary group around the optional , since ? only affects the last character. Pretty much this will look for one digit, maybe a comma, then repeat, and finally followed by a trailing /.

This can still match an odd string 1,2,3,/, so for the heck of it I improved your original regex with a negative lookbehind: (?:\d,?)+(?<!,)/$. This will assert that there is no comma directly before the trailing /.

More Related Contents:

  1. Speed up millions of regex replacements in Python 3
  2. Mass string replace in python?
  3. How do I re.search or re.match on a whole file without reading it all into memory?
  4. How to understand regular expression with python?
  5. Escaping regex string
  6. pandas loc vs. iloc vs. at vs. iat?
  7. How can I remove text within parentheses with a regex?
  8. Why is [] faster than list()?
  9. Python regular expressions – how to capture multiple groups from a wildcard expression?
  10. What’s a faster operation, re.match/search or str.find?
  11. Named regular expression group “(?Pregexp)”: what does “P” stand for?
  12. Regex matching between two strings?
  13. It is more efficient to use if-return-return or if-else-return?
  14. Most efficient way to forward-fill NaN values in numpy array
  15. Capturing group with findall?
  16. Python re.sub question
  17. Efficiently Calculating a Euclidean Distance Matrix Using Numpy
  18. How to replace the first occurrence of a regular expression in Python?
  19. How do I specify a range of unicode characters
  20. Python regex for unicode capitalized words
  21. RegExp match repeated characters
  22. Is & faster than % when checking for odd numbers?
  23. Regex, select closest match
  24. Regex to find words between two tags
  25. What is the fastest way to output large DataFrame into a CSV file?
  26. How expensive are Python dictionaries to handle?
  27. Python: UserWarning: This pattern has match groups. To actually get the groups, use str.extract
  28. Using ^ to match beginning of line in Python regex
  29. How to split long regular expression rules to multiple lines in Python
  30. Python regular expression not matching

Leave a Comment