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

Question

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

Однако после моего тестирования я заметил, что регулярное выражение '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,

Answer 1

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

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

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

Таким образом, эти два "эквивалентных" никогда не совпадающих шаблона регулярных выражений a^ а также x^ на самом деле не так эквивалентны, принимая во внимание более широкий контекст внутренней работы движка регулярных выражений и выбранные данные испытаний.