For some time I'm interested in regular expressions and Finite State Machine. Recently, I saw that Python uses "Secret Labs' Regular Expression Engine", which very often works too slow. Its pesymistic time complexity is O(2^n), although other solutions, with time complexity O(n*m) ( O(n*m^2), m is the length of the regular expression and n is the length of the text, introduction to problem: http://swtch.com/~rsc/regexp/regexp1.html ) For example: $ cat test.py import re import sys if sys.argv[1:]: n = int(sys.argv[1]) regexp = 'a?'*n + 'a'*n print 'regexp=', regexp str = 'a'*n + 'b' + 'a'*n print 'str=', str print re.findall(regexp, str) $ time python test.py 20 regexp= a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaa str= aaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaa ['aaaaaaaaaaaaaaaaaaaa', 'aaaaaaaaaaaaaaaaaaaa'] real 0m0.592s user 0m0.508s sys 0m0.028s $ time python test.py 21 regexp= a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaa str= aaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaa ['aaaaaaaaaaaaaaaaaaaaa', 'aaaaaaaaaaaaaaaaaaaaa'] real 0m1.018s user 0m1.000s sys 0m0.004s $ time python test.py 22 regexp= a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaa str= aaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaa ['aaaaaaaaaaaaaaaaaaaaaa', 'aaaaaaaaaaaaaaaaaaaaaa'] real 0m2.062s user 0m1.992s sys 0m0.028s $ time python test.py 23 regexp= a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaa str= aaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaa ['aaaaaaaaaaaaaaaaaaaaaaa', 'aaaaaaaaaaaaaaaaaaaaaaa'] real 0m4.159s user 0m4.092s sys 0m0.024s Unfortuntely not for all regular expressions quick implementation may be used (e.g. when it uses backreferences), but for major part of regular expressions this implementation works much faster. In addition to Google Summer of Code I would willingly write a faster implementation of regular expressions in Python. Naturally, the implementation would be 100% compatible with the existing regexp engine. What do you think about my proposition? -- Bartlomiej Wolowiec
Bart³omiej Wo³owiec <b.wolowiec@students.mimuw.edu.pl> wrote:
For some time I'm interested in regular expressions and Finite State Machine. Recently, I saw that Python uses "Secret Labs' Regular Expression Engine", which very often works too slow. Its pesymistic time complexity is O(2^n), although other solutions, with time complexity O(n*m) ( O(n*m^2), m is the length of the regular expression and n is the length of the text, introduction to problem: http://swtch.com/~rsc/regexp/regexp1.html )
[snip]
In addition to Google Summer of Code I would willingly write a faster implementation of regular expressions in Python. Naturally, the implementation would be 100% compatible with the existing regexp engine. What do you think about my proposition?
Submit it as a Google Summer of Code project. - Josiah
Bartlomiej Wolowiec wrote:
For some time I'm interested in regular expressions and Finite State Machine. Recently, I saw that Python uses "Secret Labs' Regular Expression Engine", which very often works too slow. Its pesymistic time complexity is O(2^n), although other solutions, with time complexity O(n*m) ( O(n*m^2), m is the length of the regular expression and n is the length of the text, introduction to problem: http://swtch.com/~rsc/regexp/regexp1.html )
that article almost completely ignores all the subtle capturing and left- to-right semantics that a perl-style engine requires, though. trust me, this is a much larger can of worms than you might expect. but if you're ready to open it, feel free to hack away.
major part of regular expressions
the contrived example you used has nothing whatsoever to do with "major part of regular expressions" as seen in the wild, though. I'd be much more interested in optimizations that focuses on patterns you've found in real code. </F>
On 3/23/07, Fredrik Lundh <fredrik@pythonware.com> wrote:
Bartlomiej Wolowiec wrote:
For some time I'm interested in regular expressions and Finite State Machine. Recently, I saw that Python uses "Secret Labs' Regular Expression Engine", which very often works too slow. Its pesymistic time complexity is O(2^n), although other solutions, with time complexity O(n*m) ( O(n*m^2), m is the length of the regular expression and n is the length of the text, introduction to problem: http://swtch.com/~rsc/regexp/regexp1.html )
that article almost completely ignores all the subtle capturing and left- to-right semantics that a perl-style engine requires, though. trust me, this is a much larger can of worms than you might expect. but if you're ready to open it, feel free to hack away.
major part of regular expressions
the contrived example you used has nothing whatsoever to do with "major part of regular expressions" as seen in the wild, though. I'd be much more interested in optimizations that focuses on patterns you've found in real code.
A fruitful direction that is not as ambitious as re-writing the entire engine would be to add "independent group" assertions to python's RE syntax [ (?> ... ) in perl]. They are rather handy for optimizing the malperforming cases alluded to here (which rarely occur as the OP posted, but tend to crop up in less malignant forms). -Mike
participants (4)
-
Bartłomiej Wołowiec -
Fredrik Lundh -
Josiah Carlson -
Mike Klaas