почему производительность отличается, если изменить порядок компиляции и findall в Python - PullRequest
Новая
       19

почему производительность отличается, если изменить порядок компиляции и findall в Python

0 голосов
/ 12 ноября 2018

Я заметил, что предварительная обработка путем компиляции шаблона ускорит операцию сопоставления, как в следующем примере. 

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

Но если я изменю порядок скомпилированного шаблона и повторного модуля, результат будет другим, теперь кажется, что это происходит намного медленнее, почему это произошло? 

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 ]

0 голосов
/ 12 ноября 2018

Предположим, что word1, word2 ... являются регулярными выражениями:

давайте перепишем эти части: 

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

Я бы создал одно регулярное выражение для всех шаблонов: 

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

Для поддержки регулярных выражений с | в них вы должны заключить в скобки выражения: 

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

(конечно, это также работает со стандартными словами, и все еще стоит использовать регулярные выражения из-за | части)

теперь это замаскированная петля с жестко закодированным каждым термином: 

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)

можно переписать просто как 

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

с точки зрения производительности:

Регулярное выражение компилируется при запуске, поэтому оно работает настолько быстро, насколько это возможно. здесь нет ни цикла, ни вставленных выражений, часть "или" выполняется механизмом регулярных выражений, который в большинстве случаев представляет собой скомпилированный код: он не может превзойти его в чистом Python. Матч и раскол делаются за одну операцию Последний сбой заключается в том, что внутренне механизм регулярных выражений ищет все выражения в цикле, что делает его алгоритмом O (n). Чтобы сделать это быстрее, вам нужно было бы предсказать, какой шаблон является наиболее частым, и поставить его на первое место (моя гипотеза состоит в том, что регулярные выражения являются «непересекающимися», что означает, что текст не может соответствовать нескольким, в противном случае самый длинный должен предшествовать более короткому)

0 голосов
/ 12 ноября 2018

Мне потребовалось некоторое время, чтобы исследовать реализацию re.findall и re.match, и я скопировал исходный код стандартной библиотеки здесь. 

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

Это показывает, что если мы выполняем re.findall (compiled_pattern, string) напрямую, это вызовет дополнительный вызов _compile (pattern, flags), в которой он будет выполнять некоторую проверку и искать шаблон в словаре кэша. Однако, если мы вместо этого вызовем compile_pattern.findall(string), эта «дополнительная операция» не будет существовать. Так что compile_pattern.findall(string) будет быстрее, чем re.findall (compile_pattern, string)

0 голосов
/ 12 ноября 2018

«Изменяя порядок», вы фактически используете findall в его «статической» форме, что эквивалентно вызову str.lower('ABC') вместо 'ABC'.lower().

В зависимости от точной реализации интерпретатора Python, который вы используете, это, вероятно, вызывает некоторые накладные расходы (например, для поиска методов).

Другими словами, это больше связано с тем, как работает Python, а не конкретно с регулярным выражением или модулем re в частности. 

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)))

Выходы 

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