efficient intersection of lists with rounding

[Steven Bethard]

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.

Steve