As answer to my question Find the 1 based position to which two lists are the same I got the hint to use the C-library itertools to speed up things.
To verify I coded the following test using cProfile:
from itertools import takewhile, izip
def match_iter(self, other):
return sum(1 for x in takewhile(lambda x: x[0] == x[1],
izip(self, other)))
def match_loop(self, other):
element = -1
for element in range(min(len(self), len(other))):
if self[element] != other[element]:
element -= 1
break
return element +1
def test():
a = [0, 1, 2, 3, 4]
b = [0, 1, 2, 3, 4, 0]
print("match_loop a=%s, b=%s, result=%s" % (a, b, match_loop(a, b)))
print("match_iter a=%s, b=%s, result=%s" % (a, b, match_iter(a, b)))
i = 10000
while i > 0:
i -= 1
match_loop(a, b)
match_iter(a, b)
def profile_test():
import cProfile
cProfile.run('test()')
if __name__ == '__main__':
profile_test()
The function match_iter() is using the itertools and the function match_loop() is the one I had implemented before using plain python.
The function test() defines two lists, prints the lists with the results of the two functions to verify it is working. Both results have the expected value 5 which is the length for the lists being equal. Then it loops 10,000 times over the both functions.
Finally the whole thing is profiled using profile_test().
What I learned than was that izip is not implemented in the itertools of python3, at least not in debian wheezy whitch I am using. So I had run the test with python2.7
Here are the results:
python2.7 match_test.py
match_loop a=[0, 1, 2, 3, 4], b=[0, 1, 2, 3, 4, 0], result=5
match_iter a=[0, 1, 2, 3, 4], b=[0, 1, 2, 3, 4, 0], result=5
180021 function calls in 0.636 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.636 0.636 <string>:1(<module>)
1 0.039 0.039 0.636 0.636 match_test.py:15(test)
10001 0.048 0.000 0.434 0.000 match_test.py:3(match_iter)
60006 0.188 0.000 0.275 0.000 match_test.py:4(<genexpr>)
50005 0.087 0.000 0.087 0.000 match_test.py:4(<lambda>)
10001 0.099 0.000 0.162 0.000 match_test.py:7(match_loop)
20002 0.028 0.000 0.028 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
10001 0.018 0.000 0.018 0.000 {min}
10001 0.018 0.000 0.018 0.000 {range}
10001 0.111 0.000 0.387 0.000 {sum}
What makes me wonder is, looking at the cumtime values, my plain python version has a value of 0.162 seconds for 10,000 loops and the match_iter version takes 0.434 seconds.
For one thing python is very fast, great, so I do not have to worry. But can this be correct, that the C-library takes more than twice as long to finish the job as simple python code? Or am I doing a fatal mistake?
To verify I ran the test with python2.6 also, which seems to be even faster, but with the same difference between looping and itertools.
Who is experienced and willing to help?
I imagine the issue here is your test lists are tiny - meaning any difference is likely to be minimal, and the cost of creating the iterators is outweighing the gains they give.
In larger tests (where the performance is more likely to matter), the version using sum() will likely outperform the other version.
Also, there is the matter of style - the manual version is longer, and relies on iterating by index, making it less flexible as well.
I would argue the most readable solution would be something like this:
def while_equal(seq, other):
for this, that in zip(seq, other):
if this != that:
return
yield this
def match(seq, other):
return sum(1 for _ in while_equal(seq, other))
Interestingly, on my system a slightly modified version of this:
def while_equal(seq, other):
for this, that in zip(seq, other):
if this != that:
return
yield 1
def match(seq, other):
return sum(while_equal(seq, other))
Performs better than the pure loop version:
a = [0, 1, 2, 3, 4]
b = [0, 1, 2, 3, 4, 0]
import timeit
print(timeit.timeit('match_loop(a,b)', 'from __main__ import a, b, match_loop'))
print(timeit.timeit('match(a,b)', 'from __main__ import match, a, b'))
Giving:
1.3171300539979711
1.291257290984504
That said, if we improve the pure loop version to be more Pythonic:
def match_loop(seq, other):
count = 0
for this, that in zip(seq, other):
if this != that:
return count
count += 1
return count
This times (using the same method as above) at 0.8548871780512854 for me, significantly faster than any other method, while still being readable. This is probably due to looping by index in the original version, which is generally very slow. I, however, would go for the first version in this post, as I feel it's the most readable.