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

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, оно будет засчитано дважды.

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

Кроме того, если бы это была огромная строка (больше 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

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

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

Answer 6

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

Answer 7

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

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

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