给定起始字符时搜索更慢令人费解

Question

我写了一个Python工具，用来扫描日志文件，寻找已知的错误模式。

我想通过给正则表达式引擎提供更多的模式信息来加快搜索速度。比如，我不仅仅是想找包含gold的行，还要求这些行必须以一个下划线开头，所以我用的是^_.*gold，而不是简单的gold。

因为99%的行都不是以下划线开头，我原本期待这样会大大提高性能，因为正则引擎可以在读取到第一个字符后就停止处理这一行。但我很惊讶地发现，结果正好相反。

下面的程序展示了这个问题：

import re
from time import time
def main():
    line = r'I do not start with an underscore 123456789012345678901234567890'
    p1 = re.compile(r"^_") # requires  underscore as a first char
    p2 = re.compile(r"abcdefghijklmnopqrstuvwxyz")
    patterns = (p1, p2)

    for p in patterns:
        start = time()
        for i in xrange(1000*1000):
            match = re.search(p, line)
        end = time() 
        print 'Elapsed: ' + str(end-start) 
main()

我尝试查看sre_compile.py来寻找解释，但它的代码对我来说太复杂了。

我在想，是否因为加入了行首字符，导致正则引擎的操作从简单的子字符串查找变成了一个更复杂的回溯状态机操作？这样反而抵消了像在第一个字符后就停止搜索的好处？

考虑到这一点，我尝试将行的长度乘以8，期待行首搜索能够表现得更好，但结果是差距只变得更大（22秒对6秒）。

我很困惑 :o 我是不是漏掉了什么？

Answer 1

有趣的观察！我试着玩了一下这个。我的猜测是，正则表达式引擎会扫描整个字符串，寻找下划线，然后在找到匹配后再对行的开头进行匹配。可能这和使用 re.MULTILINE 时的统一行为有关。

如果你用 re.match 来替代 re.search 来查找下划线模式，两者的速度似乎差不多，也就是说：

def main():
    line = r'I do not start with an underscore 123456789012345678901234567890'
    p1 = re.compile(r"_.*") # requires  underscore as a first char
    p2 = re.compile(r"abcdefghijklmnopqrstuvwxyz")
    patterns = (p1, p2)

    start = time()
    for i in xrange(1000*1000):
        match = re.match(p1, line)
    end = time() 
    print 'Elapsed: ' + str(end-start) 
    start = time()
    for i in xrange(1000*1000):
        match = re.search(p2, line)
    end = time() 
    print 'Elapsed: ' + str(end-start) 

在这种情况下，match 需要从字符串的开头开始匹配。

另外，要注意，使用预编译的模式似乎会更快：

for p in patterns:
    start = time()
    for i in xrange(1000*1000):
        match = p.search(line)
    end = time() 
    print 'Elapsed: ' + str(end-start)

不过，速度差异依然存在……

Answer 2

这样怎么样

if line[0] == "_" and "gold" in line:
   print "Yup, it starts with an underscore"
else:
   print "Nope it doesn't"

说真的，不要过度使用正则表达式

Answer 3

你其实犯了两个错误：如果你想查看字符串的开头，应该用match而不是search。另外，不要直接用re.match( pattern, line)，应该先编译模式，然后用pattern.match(line)。

import re
from time import time
def main():
    line = r'I do not start with an underscore 123456789012345678901234567890'
    p1 = re.compile(r"_") # requires  underscore as a first char
    p2 = re.compile(r"abcdefghijklmnopqrstuvwxyz")
    patterns = (p1, p2)

    for p in patterns:
        start = time()
        for i in xrange(1000*1000):
            match = p.match(line)
        end = time() 
        print 'Elapsed: ' + str(end-start) 
main()

这样你会发现现在的行为符合预期——这两种模式的运行时间是完全一样的。