python - 给出起始字符时搜索速度变慢是违反直觉的

Question

我编写了一个 Python 实用程序来扫描日志文件以查找已知错误模式。

我试图通过为正则表达式引擎提供额外的模式信息来加快搜索速度。例如，不仅我在寻找带有 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 寻找解释，但它的代码对我来说太复杂了。

是否可以通过包含行首字符将正则表达式引擎操作从简单的子字符串操作转变为更复杂的回溯状态机操作来解释观察到的性能？从而超过任何好处，例如在第一个字符后中止搜索？

这么想后，我尝试将线的长度乘以 x8，希望线搜索的开始能够发光，但差距只会变大(22 秒对 6 秒)。

我很困惑:o 我在这里遗漏了什么吗？

Answer 1

您实际上做错了两件事:如果您想查看字符串的开头，请使用 match not 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()

您将看到您现在拥有预期的行为 - 两种模式花费的时间完全相同。