efficient intersection of lists with rounding

[Diez B. Roggisch]

> A couple of other bits of info.
> - a and b are ordered smallest to largest (could bisect module be used?)
> - in the future I will want to round the second number of closest 0.25
> rather than whole number.
> 
> Would the sets module be more efficient?
> 
> I'm using python 2.3.

I'd go for something that uses the rounded versions of the lists and then
iterates the first list and lets the second "cach up". Sorry, I'm to lazy
to desribe it better, so here is the code:

a= [(123,1.3),(123,2.4),(123,7.8),(123,10.2)]
b= [(123, 0.9), (123, 1.9), (123, 8.0)]
a =  [ (i,round(j)) for i,j in a]
b =  [ (i,round(j)) for i,j in b]


res = []
pos_b = 0

try:
    for i, pivot in a:
        while b[pos_b][1] < pivot:
            pos_b += 1
        while b[pos_b][1] == pivot:
            res.append(b[pos_b])
            pos_b += 1
except IndexError:
    # If b gets exhausted somewhere
    pass
print res

While it looks more complicated, it certainly is faster, as its complexity
is in O(max(len(a), len(b))) where your code was O(len(a) * len(b)) - so
usually more or less quadratic.

The speed gain comes of course from the order of the elements. And you could
factor the rounding _into_ the loops, but thats more ugly.


-- 
Regards,

Diez B. Roggisch