# efficient intersection of lists with rounding

Steven Bethard 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
> 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.

Steve

```