On 3/23/07, Fredrik Lundh <[EMAIL PROTECTED]> 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 _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
