efficient intersection of lists with rounding
steven.bethard at gmail.com
Fri Dec 3 06:43:37 CET 2004
Michael Hoffman wrote:
> Steven Bethard wrote:
>> Well, in Python 2.3, I believe sets are implemented in Python while
>> they're implemented in C in Python 2.4.
> I think the Python 2.3 Sets implementation is likely to be quicker than
> whatever list-manipulation answer you come up with instead. But there's
> only one way to find out ;)
Yeah, almost certainly since he's looking at lists 3K long. If they
were small, you never know since the list comprehension gets the C-code
speedup, while sets.Set is Python code:
> python -m timeit -s "a = [(123,1.3),(123,2.4),(123,7.8),(123,10.2)];
b = [(123, 0.9), (123, 1.9), (123, 8.0)]" "[ (i,round(j)) for i,j in a
for l,m in b if (i,round(j)) == (l,round(m))]"
10000 loops, best of 3: 27.5 usec per loop
> python -m timeit -s "import sets; a =
[(123,1.3),(123,2.4),(123,7.8),(123,10.2)]; b = [(123, 0.9), (123, 1.9
), (123, 8.0)]" "sets.Set([(i,round(j)) for i,j in
a]).intersection(sets.Set([(i, round(j)) for i, j in b]))"
10000 loops, best of 3: 47.7 usec per loop
In the case given, the O(n**2) list comprehension is faster than the
O(n) set intersection. Of course, this is not likely to be true with
any reasonable sized data. But it's something worth keeping in mind.
More information about the Python-list