On 16/07/2013 16:41, Eli Bendersky wrote:

On Tue, Jul 16, 2013 at 8:00 AM, MRAB <python@mrabarnett.plus.com

<mailto:python@mrabarnett.plus.com>> wrote:

    On 16/07/2013 04:10, Eli Bendersky wrote:

        Since the 'regex' module is a candidate for inclusion into the
        stdlib, I
        figured this would be a good place to ask.

        While discussing something related in pss

        (https://github.com/eliben/pss__), Ben Hoyt brought to my

        attention that
        the implementation of alternation (foo|bar) in Python's default
        regex
        module (the SRE implementation) is very inefficient. And indeed,
        looking
        there it seems that | gets translated to an opcode that simply means
        going over all the alternatives in a loop trying to match each.
        This is
        not how a proper regex engine should implement alternation!

        A common advice given to Python programmers is to combine their
        regexes
        into a single one with |. This makes code faster, but it turns
        out that
        it's far from its full potential because the combination doesn't
        go full
        way to the DFA as it's supposed to.

        A question about 'regex' - is it implemented properly there?

    There are 2 ways of implementing regex: DFA and NFA.

    DFA is faster, but those using NFA do so because the implementation
    offers additional features that make DFA tricky or impossible, such as
    backreferences.

    Of course, you could use DFA when it's possible, NFA when it isn't, at
    the cost of yet more code.

    The regex module uses NFA, just like re.

    If you want to improve regex, making it use DFA when possible, well,
    the source code is open, and your contributions are welcome. Good luck!
    :-)


You can use NFA without backtracking, though, by keeping track of the
set of possible states. I believe (but am not 100% sure) this is the way
re2 works, for example.

In the particular case of alternations, such approach is vastly superior
because the "possible states" set never grows large (assuming the
alternatives are not mostly the same). Whereas with backtracking you
always have to iterate over all of them.

That said, I think you have answered my question - regex also uses a
backtracking implementation of NFA and iterates in case of alternations.
OK :-)

Have you tried timing them (re, re2, regex, and possibly others) to see whether
it's a problem in practice?