Резкое различие в "эквивалентном" никогда не совпадающем регулярном выражении?

Недавно я приурочил кучу регулярных выражений для вопроса "Regex, который никогда не будет соответствовать никем" (my ответьте здесь, см. дополнительную информацию).

Однако после моего тестирования я заметил, что регулярное выражение 'a^' и 'x^' потребовало совершенно разных времен, чтобы проверить, хотя они должны быть идентичными. (Только случайно я даже переключил персонажа.) Эти тайминги ниже.

In [1]: import re

In [2]: with open('/tmp/longfile.txt') as f:
   ...:     longfile = f.read()
   ...:     

In [3]: len(re.findall('\n',longfile))
Out[3]: 275000

In [4]: len(longfile)
Out[4]: 24733175

...

In [45]: %timeit re.search('x^',longfile)
6.89 ms ± 31.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [46]: %timeit re.search('a^',longfile)
37.2 ms ± 739 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [47]: %timeit re.search(' ^',longfile)
49.8 ms ± 844 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Онлайн-тестирование (только с первых 50 строк) показывает то же поведение (1441880 шагов и ~ 710 мс только с 40858 шагов и ~ 113 мс): https://regex101.com/r/AwaHmK/1

Что здесь делает Python, который делает 'a^' намного длиннее 'x^'?

Чтобы увидеть, что происходит внутри timeit или IPython, я сам написал простую функцию синхронизации, и все проверяет:

In [57]: import time

In [59]: import numpy as np

In [62]: def timing(regex,N=7,n=100):
    ...:     tN = []
    ...:     for i in range(N):
    ...:         t0 = time.time()
    ...:         for j in range(n):
    ...:             re.search(regex,longfile)
    ...:         t1 = time.time()
    ...:         tN.append((t1-t0)/n)
    ...:     return np.mean(tN)*1000, np.std(tN)*1000
    ...: 

In [63]: timing('a^')
Out[63]: (37.414282049451558, 0.33898056279589844)

In [64]: timing('x^')
Out[64]: (7.2061508042471756, 0.22062989840321218)

Я также воспроизвел мои результаты за пределами IPython в стандартной оболочке 3.5.2. Таким образом, странность не ограничена ни IPython, ни timeit.

Ответы

Ответ 1

Как упоминалось в связанном вопросе, это регулярное выражение просматривает весь текст.

Разница, которую вы видите, просто потому, что a является такой общей буквой в тексте на английском языке, и вы использовали "читаемые" данные. Итак, если вы изучите, как работают двигатели регулярных выражений, вы поймете: использование a^ вызывает еще много задержек из-за поиска предварительных совпадений в первом a, которые затем будут отклоняться позже. Поскольку x является необычным в корпусе, он тратит меньше времени - больше позиций в тексте может быть немедленно отброшено.

  • Если вы используете другую общую букву на английском языке в своем шаблоне, например e^, она будет такой же медленной (e будет, вероятно, еще медленнее, чем a).
  • Если вы используете случайные байты вместо реального текста, то как шаблоны x^, так и a^ будут работать аналогичным образом.

Итак, ваши два эквивалентных шаблона регулярных выражений, не соответствующих друг другу, не так эквивалентны. Двигатель имеет две "головки считывания", которые перемещаются слева направо - один движется в строке, один перемещается по шаблону регулярных выражений - и с шаблоном a^ в сочетании с вашим выбором данных, двигатель регулярных выражений должен делать больше Работа.