python - “等效”永不匹配的正则表达式的时间截然不同吗?

原文 标签 python regex performance

我最近为问题“A Regex that will never be matched by anything”(有关详细信息,请参阅)计时了一堆正则表达式。
然而,在我的测试之后,我注意到regex'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步和~710ms,而只有40858步和~113ms):my answer here
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之外的标准外壳中复制了我的结果。因此,这种奇怪的现象并不局限于IPython或3.5.2

最佳答案

如链接问题中所述,此regex扫描整个文本。
这里看到的时间差异仅仅是因为“a”在英语文本中是如此常见的字母,而您使用的是可读的数据。因此,如果您研究regex引擎是如何工作的,您将理解:使用模式a^会由于在第一个“a”上找到临时匹配项而导致更多的延迟,随后会被拒绝。引擎有两个“读取头”,它们都从左到右移动-一个在字符串中移动,另一个在regex模式中移动。结合使用a^模式和您选择的人类可读数据,regex引擎必须做更多的工作。由于“x”在语料库中是一个不常见的字母,因此使用模式会浪费更少的时间-文本中的更多位置可以立即被拒绝。
如果你用另一个常用字母开始这个模式,比如“e”,它也会同样慢(使用x^甚至比e^慢,因为“e”在英语中出现的频率更高)。
如果对语料库使用随机的ascii字节,而不是真正的文本,那么a^a^模式将执行类似的操作。
总之,考虑到regex引擎的内部工作环境和所选的测试数据,这两个从不匹配的regex模式x^a^实际上并不等同。

关于python - “等效”永不匹配的正则表达式的时间截然不同吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47118220/

相关文章:

android - 十进制输入过滤器android

arrays - 将字母替换为数组

javascript - 从AJAX创建时卡住 Bootstrap

java - 对象变为空

python - Pandas 数据帧中的不同连续 block

python - Python中文件的动态名称

python - 比较 SQLAlchemy ORM 中两列之间的差异

python - matplotlib在符号后面显示错误栏

java - 提取单词“Class”之后的所有第一个单词

c# - 使用Linq搜索任何单词