efficient intersection of lists with rounding

[Greg Ewing]

Gordon Williams wrote:
>>>>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))]

d = {}
for (l, m) in b:
   d[l, round(m)] = 1

result = []
for (i, j) in a:
   t = (i, round(j))
   if t in d:
     result.append(t)

> - in the future I will want to round the second number of closest 0.25
> rather than whole number.

I would do that by multiplying by 4 and rounding to
an integer to derive the dictionary key. That will
avoid any float-representation problems you might have
by trying to round to a fraction.

> Would the sets module be more efficient?

As another poster said, sets are implemented as dicts
in 2.3, so it comes down to much the same thing. Using
sets might be a bit faster than the above code in 2.4,
but probably not greatly so. By far the biggest
improvement will come from using an O(n) algorithm
instead of an O(n**2) one.

-- 
Greg Ewing, Computer Science Dept,
University of Canterbury,	
Christchurch, New Zealand
http://www.cosc.canterbury.ac.nz/~greg