Регулярное выражение '|' оператор против отдельных прогонов для каждого подвыражения

Question

У меня есть довольно большая строка (~700k), для которой мне нужно запустить 10 регулярных выражений и подсчитать все совпадения любого из регулярных выражений. Моя быстрая и грязная задача заключалась в том, чтобы сделать что-то вроде re.search('(expr1)|(expr2)|...'), но мне было интересно, увидим ли мы прирост производительности при сравнении в цикле:

Другими словами, я хочу сравнить производительность:

def CountMatchesInBigstring(bigstring, my_regexes):
  """Counts how many of the expressions in my_regexes match bigstring."""
  count = 0
  combined_expr = '|'.join(['(%s)' % r for r in my_regexes])
  matches = re.search(combined_expr, bigstring)
  if matches:
    count += NumMatches(matches)
  return count

против

def CountMatchesInBigstring(bigstring, my_regexes):
  """Counts how many of the expressions in my_regexes match bigstring."""
  count = 0
  for reg in my_regexes:
    matches = re.search(reg, bigstring)
    if matches:
      count += NumMatches(matches)
  return count

Я перестану лениться и проведу завтра несколько тестов (и опубликую результаты), но мне было интересно, выскочит ли ответ кому-то, кто действительно понимает, как работают регулярные выражения:)

Answer 1

Две вещи дадут немного разные результаты, если только не будет гарантировано, что совпадение будет соответствовать одному и только одному регулярному выражению. В противном случае, если что-то соответствует 2, оно будет засчитано дважды.

Теоретически ваше решение должно быть более быстрым (если выражение является взаимоисключающим), потому что компилятор регулярного выражения должен иметь возможность сделать более эффективный механизм поиска, поэтому требуется только один проход. Я ожидаю, что разница будет крошечной, если только выражения не очень похожи.

Кроме того, если бы это была огромная строка (больше, чем 700 КБ), можно было бы получить выгоду от выполнения одного прохода, и поэтому потребовался бы фактор n меньшего количества перестановок памяти (для кэша диска или процессора).

Моя ставка в ваших тестах это не очень заметно, хотя. Меня интересует реальный результат - пожалуйста, опубликуйте результаты.

Answer 2

Чтобы понять, как работает модуль re - скомпилируйте _sre.c в режиме отладки (поместите #define VERBOSE в строку 103 в _sre.c и перекомпилируйте python). После этого вы увидите что-то вроде этого:

>>> import re
>>> p = re.compile('(a)|(b)|(c)')
>>> p.search('a'); print '\n\n'; p.search('b')
|0xb7f9ab10|(nil)|SEARCH
prefix = (nil) 0 0
charset = (nil)
|0xb7f9ab1a|0xb7fb75f4|SEARCH
|0xb7f9ab1a|0xb7fb75f4|ENTER
allocating sre_match_context in 0 (32)
allocate/grow stack 1064
|0xb7f9ab1c|0xb7fb75f4|BRANCH
allocating sre_match_context in 32 (32)
|0xb7f9ab20|0xb7fb75f4|MARK 0
|0xb7f9ab24|0xb7fb75f4|LITERAL 97
|0xb7f9ab28|0xb7fb75f5|MARK 1
|0xb7f9ab2c|0xb7fb75f5|JUMP 20
|0xb7f9ab56|0xb7fb75f5|SUCCESS
discard data from 32 (32)
looking up sre_match_context at 0
|0xb7f9ab1c|0xb7fb75f4|JUMP_BRANCH
discard data from 0 (32)
|0xb7f9ab10|0xb7fb75f5|END




|0xb7f9ab10|(nil)|SEARCH
prefix = (nil) 0 0
charset = (nil)
|0xb7f9ab1a|0xb7fb7614|SEARCH
|0xb7f9ab1a|0xb7fb7614|ENTER
allocating sre_match_context in 0 (32)
allocate/grow stack 1064
|0xb7f9ab1c|0xb7fb7614|BRANCH
allocating sre_match_context in 32 (32)
|0xb7f9ab20|0xb7fb7614|MARK 0
|0xb7f9ab24|0xb7fb7614|LITERAL 97
discard data from 32 (32)
looking up sre_match_context at 0
|0xb7f9ab1c|0xb7fb7614|JUMP_BRANCH
allocating sre_match_context in 32 (32)
|0xb7f9ab32|0xb7fb7614|MARK 2
|0xb7f9ab36|0xb7fb7614|LITERAL 98
|0xb7f9ab3a|0xb7fb7615|MARK 3
|0xb7f9ab3e|0xb7fb7615|JUMP 11
|0xb7f9ab56|0xb7fb7615|SUCCESS
discard data from 32 (32)
looking up sre_match_context at 0
|0xb7f9ab2e|0xb7fb7614|JUMP_BRANCH
discard data from 0 (32)
|0xb7f9ab10|0xb7fb7615|END

>>>                                      

Answer 3

Я верю, что ваша первая реализация будет быстрее:

• Один из ключевых принципов производительности Python - это "переместить логику на уровень C" - это означает, что встроенные функции (написанные на C) работают быстрее, чем реализации на чистом Python. Таким образом, когда цикл выполняется встроенным модулем Regex, он должен быть быстрее
• Одно регулярное выражение может искать несколько шаблонов за один проход, а это означает, что ему нужно всего лишь один раз просмотреть содержимое файла, тогда как нескольким регулярным выражениям придется читать весь файл несколько раз.

Answer 4

Я подозреваю, что регулярное выражение также будет делать то, что вы пытаетесь сделать... только намного лучше:)

так что "|" победит

Answer 5

Одна компиляция и поиск должны давать более быстрые результаты, при более низкой шкале выражений выигрыш может быть незначительным, но чем больше вы пробегаете, тем больше выигрыш. Думайте об этом как о компиляции один раз и сопоставлении против компиляции 10 раз и сопоставлении.

Answer 6

Чем меньше проходов, тем лучше: он просто использует больше памяти, что, как правило, не является проблемой.

Если интерпретатору может быть предоставлено что-либо для обработки, он всегда найдет более быстрое решение (как по времени реализации, так и по времени выполнения), чем у обычного человека.

Answer 7

Я согласен с amartynov, но я хотел бы добавить, что вы также могли бы сначала скомпилировать регулярное выражение (re.compile()), особенно. во втором варианте, как тогда, вы можете сэкономить некоторое время установки в цикле. Может быть, вы можете измерить это, пока вы на нем.

Причина, по которой я думаю, что один выстрел работает лучше, заключается в том, что я предполагаю, что он полностью сделан в C-пространстве и что не нужно много интерпретировать код Python.

Но с нетерпением жду цифры.