[issue11307] re engine exhaustively explores more than necessary

Terry J. Reedy added the comment: 13 secs on my 7 year old windows machine. -- nosy: +terry.reedy resolution: -> duplicate status: open -> closed superseder: -> the re module can perform poorly: O(2**n) versus O(n**2) versions: +Python 2.7, Python 3.3 -Python 2.6, Python 3.1

[issue11307] re engine exhaustively explores more than necessary

Matthew Barnett added the comment: It's a known issue (see issue #1662581, for example). There's a new implementation at PyPI which doesn't have this problem: http://pypi.python.org/pypi/regex -- nosy: +mrabarnett ___ Python tracker

[issue11307] re engine exhaustively explores more than necessary

New submission from Niko Matsakis : Executing code like this: >>> r = re.compile(r'(\w+)*=.*') >>> r.match("abcdefghijklmnopqrstuvwxyz") takes a long time (around 12 seconds, on my machine). Presumably this is because it is enumerating all the various ways to divvy up the alphabet for (\w+),