re.match与re.search的性能差异

Question

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

>>> 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代码后，我得到了与他相似的结果。

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

那么，现在更新的问题是，为什么search的性能优于match？

Answer 1

"所以，现在更新的问题是为什么搜索不匹配？">

在这个使用文本字符串而不是正则表达式模式的特定实例中，对于默认的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代码，搜索代码似乎有一个内置的优化功能，可以快速匹配以字符串横向为前缀的模式。在上面的例子中，整个模式是一个没有regex模式的文字字符串，因此这个优化的routined用于匹配整个模式。

注意，一旦我们引入regex符号，性能就会下降，并且随着文字字符串前缀变短：

>>> print timeit.timeit(stmt="r.search(s)",
...              setup="import re; s = 'helloab'*100000; r = re.compile('hell.')",
...             number = 10000000)
3.20765399933
>>> 
>>> print timeit.timeit(stmt="r.search(s)",
...              setup="import re; s = 'helloab'*100000; r = re.compile('hel.o')",
...             number = 10000000)
3.31512498856
>>> print timeit.timeit(stmt="r.search(s)",
...              setup="import re; s = 'helloab'*100000; r = re.compile('he.lo')",
...             number = 10000000)
3.31983995438
>>> print timeit.timeit(stmt="r.search(s)",
...              setup="import re; s = 'helloab'*100000; r = re.compile('h.llo')",
...             number = 10000000)
3.39261603355

对于包含正则表达式模式的部分模式，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才比re.match快。

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

>>> # 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