21

I tried to compare re.match and re.search using timeit module and I found that match was better than search when the string I want to found was at the beginning of the string.

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

Now, I am aware that match looks for the pattern in the beginning of the string and return an object if found but what I am wondering is how does search operate.

Does search performs any extra matching after the string is found in the beginning which slows it down?

Update

After using @David Robinsons code I got results simlar to him.

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

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

6
  • 8
    You really should construct the test string and the regex object in the setup parameter to timeit so that you are only measuring the match/search itself. And do a lot more than 10 iterations.
    – interjay
    Oct 9, 2012 at 15:47
  • @interjay: Increased it to 10000. Tried number=100000 but on my netbook it was taking way too much time.
    – RanRag
    Oct 9, 2012 at 15:55
  • 2
    ...but you didn't do the other things I said, so you aren't measuring anything significant to your question (most of the time is spent constructing the string).
    – interjay
    Oct 9, 2012 at 15:57
  • @interjay: Actually this is the first time I have used timeit. So, currently reading the docs on how to move import and string construction out of setup.
    – RanRag
    Oct 9, 2012 at 16:00
  • @Noob: See my answer for an example (might be worth running my code on your machine) Oct 9, 2012 at 16:02

2 Answers 2

20

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

In this particular instance where a literal string is used rather than a regex pattern, indeed re.search is slightly faster than re.match for the default CPython implementation (I have not tested this in other incarnations of 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

Looking into the C code behind those modules, it appears the search code has a built in optimisation to quickly match patterns prefixed with a string lateral. In the example above, the whole pattern is a literal string with no regex patterns and so this optimised routined is used to match the whole pattern.

Notice how the performance degrades once we introduce regex symbols and, as the literal string prefix gets shorter:

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

For portion of the pattern that contain regex patterns, SRE_MATCH is used to determine matches. That is essentially the same code behind re.match.

Note how the results are close (with re.match marginally faster) if the pattern starts with a regex pattern instead of a literal string.

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

In other words, ignoring the fact that search and match have different purposes, re.search is faster than re.match only when the pattern is a literal string.

Of course, if you're working with literal strings, you're likely to be better off using string operations instead.

>>> # 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
1
  • Fantastic research and experimentation. Thank you especially for including links to the source. Dec 9, 2014 at 6:43
7

On my machine (Python 2.7.3 on Mac OS 10.7.3, 1.7 GHz Intel Core i5), when done putting the string construction, importing re, and the regex compiling in setup, and performing 10000000 iterations instead of 10, I find the opposite:

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
9
  • 1
    I confirm this result. (OS X 10.5.8, python 2.7.3) I get that search is approximately 25% faster.
    – mgilson
    Oct 9, 2012 at 15:57
  • As noted in edit, I find the gap increases if the regex compiling is done in the setup statement. Oct 9, 2012 at 16:01
  • 1
    I have similar results at my Linux box(Archlinux, python 2.7.3), but why search is faster than match? Interesting that python 3.2.3 executes the same tests about 40.8 and 37.3 seconds(python 2.7 -> 16.7 and 14.0) at by box, it's about 2.5 times slower! Oct 9, 2012 at 16:02
  • Shouldn't that be r.match(s) and r.search(s)? (not that it would make much difference to performance in this case since the matching string appears right at the beginning).
    – Shawn Chin
    Oct 9, 2012 at 16:07
  • 1
    @Noob: Not yet. Still considering. Oct 9, 2012 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.