重新匹配与搜索性能差异

Question

我试图使用timeit模块比较re.match和{}，我发现当我要查找的字符串位于字符串的开头时，匹配比搜索更好。在

>>> s1 = '''
... import re
... re.search(r'hello','helloab'*100000)
... '''
>>> timeit.timeit(stmt=s1,number=10000)
32.12064480781555


>>> s = '''
... import re
... re.match(r'hello','helloab'*100000)
... '''
>>> timeit.timeit(stmt=s,number=10000)
30.9136700630188

现在，我知道match会在字符串的开头查找模式，如果找到就返回一个对象，但是我想知道的是搜索是如何操作的。在

搜索是否会在开始时找到字符串后执行任何额外的匹配，从而减慢搜索速度？在

更新

在使用了@David Robinsons代码后，我得到了与他相似的结果。在

^{pr2}$

所以，更新后的问题是为什么search表现不佳match？在

Answer 1

"So, the updated question is now why search is out-performing match?"

在这个使用文本字符串而不是regex模式的特定实例中，对于默认CPython实现，re.search确实比re.match稍快一些（我没有在Python的其他实例中测试过这一点）。在

>>> print timeit.timeit(stmt="r.match(s)",
...              setup="import re; s = 'helloab'*100000; r = re.compile('hello')",
...              number = 10000000)
3.29107403755
>>> print timeit.timeit(stmt="r.search(s)",
...              setup="import re; s = 'helloab'*100000; r = re.compile('hello')",
...             number = 10000000)
2.39184308052

查看C code behind those modules，搜索代码似乎有一个内置的优化to quickly match patterns prefixed with a string lateral。在上面的例子中，整个模式是一个没有正则表达式模式的文本字符串，因此这个经过优化的路由用于匹配整个模式。在

请注意，一旦我们引入正则表达式符号，并且随着字符串前缀变短，性能将如何降低：

^{pr2}$

对于包含regex模式的部分模式，SRE_MATCH用于确定匹配项。这与re.match后面的代码基本相同。在

注意，如果模式以regex模式而不是文本字符串开始，那么结果是如何接近的（与re.match稍微快一点）。在

>>> print timeit.timeit(stmt="r.match(s)",
...              setup="import re; s = 'helloab'*100000; r = re.compile('.ello')",
...              number = 10000000)
3.22782492638
>>> print timeit.timeit(stmt="r.search(s)",
...              setup="import re; s = 'helloab'*100000; r = re.compile('.ello')",
...             number = 10000000)
3.31773591042

---

换句话说，忽略search和match有不同的目的，只有当模式是文本字符串时，re.search比{}快。在

当然，如果使用的是文本字符串，那么使用字符串操作可能会更好。在

>>> # Detecting exact matches
>>> print timeit.timeit(stmt="s == r", 
...              setup="s = 'helloab'*100000; r = 'hello'", 
...              number = 10000000)
0.339027881622

>>> # Determine if string contains another string
>>> print timeit.timeit(stmt="s in r", 
...              setup="s = 'helloab'*100000; r = 'hello'", 
...              number = 10000000)
0.479326963425


>>> # detecting prefix
>>> print timeit.timeit(stmt="s.startswith(r)",
...              setup="s = 'helloab'*100000; r = 'hello'",
...             number = 10000000)
1.49393510818
>>> print timeit.timeit(stmt="s[:len(r)] == r",
...              setup="s = 'helloab'*100000; r = 'hello'",
...             number = 10000000)
1.21005606651

Answer 2

在我的机器（Mac OS 10.7.3上的Python 2.7.3，1.7 GHz Intel Core i5）上，当完成字符串构造、导入re和regex编译并执行10000000次迭代（而不是10次）后，我发现相反的情况：

import timeit

print timeit.timeit(stmt="r.match(s)",
             setup="import re; s = 'helloab'*100000; r = re.compile('hello')",
             number = 10000000)
# 6.43165612221
print timeit.timeit(stmt="r.search(s)",
             setup="import re; s = 'helloab'*100000; r = re.compile('hello')",
            number = 10000000)
# 3.85176897049