python - "equivalent"永不匹配的正则表达式的时间截然不同？

Question

我最近为问题“A Regex that will never be matched by anything ”( my answer here ，请参阅更多信息)计时了一堆正则表达式。

然而，在我测试之后，我注意到正则表达式 '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 shell 中复制了我的结果。所以奇怪的是不局限于 IPython 或 timeit。

Answer 1

如链接问题中所述，此正则表达式会扫描整个文本。

这里看到的时间差异只是因为“a”在英文文本中是一个很常见的字母，而您使用了可读数据。所以，如果你研究正则表达式引擎是如何工作的，你就会明白:使用模式 a^ 会导致更多的延迟，因为在第一个“a”上找到试探性匹配，然后被拒绝。该引擎有两个“读取头”，它们都从左向右移动——一个在字符串中移动，另一个在正则表达式模式中移动。将 a^ 模式与您选择的人类可读数据结合使用，正则表达式引擎必须做更多的工作。由于“x”在语料库中是一个不常见的字母，使用模式 x^ 浪费的时间更少 - 文本中的更多位置可以立即被拒绝。

• 如果模式以另一个常见字母开头，例如“e”，它会同样慢(使用 e^ 会比 a^ 更慢，因为“e”在英语中出现的频率更高)。
• 如果您对语料库使用随机 ascii 字节而不是真实文本，则 a^ 和 x^ 模式的表现将相似。

总而言之，考虑到正则表达式的更广泛上下文，这两个“等效”的永不匹配的正则表达式模式 a^ 和 x^ 实际上并不那么等效引擎的内部工作原理和选择的测试数据。