why the performance different if change the order of compile and findall in python

Viewed 197

I notice that preprocessing by compiling pattern will speed up the match operation, just like the following example.

python3 -m timeit -s "import re; t = re.compile(r'[\w+][\d]+')" "t.findall('abc eft123&aaa123')"

1000000 loops, best of 3: 1.42 usec per loop

python3 -m timeit -s "import re;" "re.findall(r'[\w+][\d]+', 'abc eft123&aaa123')"

100000 loops, best of 3: 2.45 usec per loop

But if I change the order of compiled pattern and re module, the result different, it seems that much slower now, why this happened?

python3 -m timeit -s "import re; t = re.compile(r'[\w+][\d]+')" "re.findall(t, 'abc eft123&aaa123')"

100000 loops, best of 3: 3.66 usec per loop

3 Answers

By "changing the order" you are actually using findall in its "static" form, pretty much the equivallent of calling str.lower('ABC') instead of 'ABC'.lower().

Depending on the exact implementation of the Python interpreter you are using, this is probably causing some overhead (for method lookups for example).

In other words, this is more related to the way Python works and not specifically to regex or the re module in particular.

from timeit import Timer

def a():
    str.lower('ABC')

def b():
    'ABC'.lower()

print(min(Timer(a).repeat(5000, 5000)))
print(min(Timer(b).repeat(5000, 5000)))

Outputs

0.001060427000000086    # str.lower('ABC')
0.0008686820000001205   # 'ABC'.lower()

Let's say that word1, word2 ... are regexes:

let's rewrite those parts:

allWords = [re.compile(m) for m in ["word1", "word2", "word3"]]

I would create one single regex for all patterns:

allWords = re.compile("|".join(["word1", "word2", "word3"])

To support regexes with | in them, you would have to parenthesize the expressions:

allWords = re.compile("|".join("({})".format(x) for x in ["word1", "word2", "word3"])

(that also works with standard words of course, and it's still worth using regexes because of the | part)

now this is a disguised loop with each term hardcoded:

def bar(data, allWords):
   if allWords[0].search(data) != None:
      temp = data.split("word1", 1)[1]  # that works only on non-regexes BTW
      return(temp)

   elif allWords[1].search(data) != None:
      temp = data.split("word2", 1)[1]
      return(temp)

can be rewritten simply as

def bar(data, allWords):
   return allWords.split(data,maxsplit=1)[1]

in terms of performance:

Regular expression is compiled at start, so it's as fast as it can be there's no loop or pasted expressions, the "or" part is done by the regex engine, which is most of the time some compiled code: can't beat that in pure python. The match & the split are done in one operation The last hiccup is that internally the regex engine searches for all expressions in a loop, which makes that a O(n) algorithm. To make it faster, you would have to predict which pattern is the most frequent, and put it first (my hypothesis is that regexes are "disjoint", which means that a text cannot be matched by several ones, else the longest would have to come before the shorter one)

I took some time to investigate the realization of re.findall and re.match, and I copied the standard library source code here.

def findall(pattern, string, flags=0):
    """Return a list of all non-overlapping matches in the string.

    If one or more capturing groups are present in the pattern, return
    a list of groups; this will be a list of tuples if the pattern
    has more than one group.

    Empty matches are included in the result."""
    return _compile(pattern, flags).findall(string)


def match(pattern, string, flags=0):
    """Try to apply the pattern at the start of the string, returning
    a match object, or None if no match was found."""
    return _compile(pattern, flags).match(string)


def _compile(pattern, flags):
    # internal: compile pattern
    try:
        p, loc = _cache[type(pattern), pattern, flags]
        if loc is None or loc == _locale.setlocale(_locale.LC_CTYPE):
            return p
    except KeyError:
        pass
    if isinstance(pattern, _pattern_type):
        if flags:
            raise ValueError(
                "cannot process flags argument with a compiled pattern")
        return pattern
    if not sre_compile.isstring(pattern):
        raise TypeError("first argument must be string or compiled pattern")
    p = sre_compile.compile(pattern, flags)
    if not (flags & DEBUG):
        if len(_cache) >= _MAXCACHE:
            _cache.clear()
        if p.flags & LOCALE:
            if not _locale:
                return p
            loc = _locale.setlocale(_locale.LC_CTYPE)
        else:
            loc = None
        _cache[type(pattern), pattern, flags] = p, loc
    return p

This shows that if we execute re.findall(compiled_pattern, string) directly, it will trigger an additional calling of _compile(pattern, flags), in which function it will do some check and search the pattern in cache dictionary. However, if we call compile_pattern.findall(string) instead, that 'additional operation' wouldn't exist. So compile_pattern.findall(string) will faster than re.findall(compile_pattern, string)

Related