efficient intersection of lists with rounding

[Gordon Williams]

Hi,

I have to lists that I need to find the common numbers (2nd rounded to
nearest integral) and I am wondering if there is a more efficient way of
doing it.
[color=blue][color=green][color=darkred]
>>> 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)) ==[/color][/color][/color]
(l,round(m))]
[(123, 1.0), (123, 2.0), (123, 8.0)][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]
This works but a and b can be in the order of 30K long.

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.

Thanks for any ideas.

Regards,

Gordon Williams

[Diez B. Roggisch]

Re: efficient intersection of lists with rounding

> A couple of other bits of info.[color=blue]
> - 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.[/color]

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

[Steven Bethard]

Re: efficient intersection of lists with rounding

Gordon Williams wrote:[color=blue]
> I have to lists that I need to find the common numbers (2nd rounded to
> nearest integral) and I am wondering if there is a more efficient way of
> doing it.
>[color=green][color=darkred]
>>>>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)) ==[/color][/color]
>
> (l,round(m))]
> [(123, 1.0), (123, 2.0), (123, 8.0)]
>[/color]
[snip][color=blue]
> Would the sets module be more efficient?[/color]

Well, in Python 2.3, I believe sets are implemented in Python while
they're implemented in C in Python 2.4. So probably not, unless you
upgrade. A 2.4 solution with sets:
[color=blue][color=green][color=darkred]
>>> a = [(123,1.3),(123, 2.4),(123,7.8), (123,10.2)]
>>> b = [(123, 0.9), (123, 1.9), (123, 8.0)]
>>> def roundedj(pairs_ iterable):[/color][/color][/color]
.... return ((i, round(j)) for i, j in pairs_iterable)
....[color=blue][color=green][color=darkred]
>>> set(roundedj(a) ).intersection( set(roundedj(b) ))[/color][/color][/color]
set([(123, 8.0), (123, 2.0), (123, 1.0)])

Steve

[Diez B. Roggisch]

Re: efficient intersection of lists with rounding

> A couple of other bits of info.[color=blue]
> - 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.[/color]

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

[Steven Bethard]

Re: efficient intersection of lists with rounding

Gordon Williams wrote:[color=blue]
> I have to lists that I need to find the common numbers (2nd rounded to
> nearest integral) and I am wondering if there is a more efficient way of
> doing it.
>[color=green][color=darkred]
>>>>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)) ==[/color][/color]
>
> (l,round(m))]
> [(123, 1.0), (123, 2.0), (123, 8.0)]
>[/color]
[snip][color=blue]
> Would the sets module be more efficient?[/color]

Well, in Python 2.3, I believe sets are implemented in Python while
they're implemented in C in Python 2.4. So probably not, unless you
upgrade. A 2.4 solution with sets:
[color=blue][color=green][color=darkred]
>>> a = [(123,1.3),(123, 2.4),(123,7.8), (123,10.2)]
>>> b = [(123, 0.9), (123, 1.9), (123, 8.0)]
>>> def roundedj(pairs_ iterable):[/color][/color][/color]
.... return ((i, round(j)) for i, j in pairs_iterable)
....[color=blue][color=green][color=darkred]
>>> set(roundedj(a) ).intersection( set(roundedj(b) ))[/color][/color][/color]
set([(123, 8.0), (123, 2.0), (123, 1.0)])

Steve

[Michael Hoffman]

Re: efficient intersection of lists with rounding

Steven Bethard wrote:
[color=blue]
> Well, in Python 2.3, I believe sets are implemented in Python while
> they're implemented in C in Python 2.4.[/color]

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 ;)
--
Michael Hoffman

[Michael Hoffman]

Re: efficient intersection of lists with rounding

Steven Bethard wrote:
[color=blue]
> Well, in Python 2.3, I believe sets are implemented in Python while
> they're implemented in C in Python 2.4.[/color]

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 ;)
--
Michael Hoffman

[Greg Ewing]

Re: efficient intersection of lists with rounding

Gordon Williams wrote:[color=blue][color=green][color=darkred]
>>>>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)) ==[/color][/color]
> (l,round(m))][/color]

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 )
[color=blue]
> - in the future I will want to round the second number of closest 0.25
> rather than whole number.[/color]

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.
[color=blue]
> Would the sets module be more efficient?[/color]

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

[Greg Ewing]

Re: efficient intersection of lists with rounding

Gordon Williams wrote:[color=blue][color=green][color=darkred]
>>>>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)) ==[/color][/color]
> (l,round(m))][/color]

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 )
[color=blue]
> - in the future I will want to round the second number of closest 0.25
> rather than whole number.[/color]

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.
[color=blue]
> Would the sets module be more efficient?[/color]

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

[Adam DePrince]

Re: efficient intersection of lists with rounding

On Thu, 2004-12-02 at 22:16, Greg Ewing wrote:[color=blue]
> Gordon Williams wrote:[color=green][color=darkred]
> >>>>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)) ==[/color]
> > (l,round(m))][/color]
>
> 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 )
>[color=green]
> > - in the future I will want to round the second number of closest 0.25
> > rather than whole number.[/color]
>
> 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.
>[color=green]
> > Would the sets module be more efficient?[/color]
>
> 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.[/color]

Of course a low O-factor is important; you should avoid however
confusing the statement of what you want to do with the statement of how
you want to do it. One of the benefits of a HLL like Python is you can
merely state *what* you want without worrying about how to compute it.

In the original example above you are computing a set intersection -
python's set object has an intersection method. Use it. Not only is it
faster than your O**2 solution, but it is a good deal clearer.
[color=blue][color=green][color=darkred]
>>> from sets import Set
>>> set_a = Set( [(i,round(j)) for i,j in a] )
>>> set_b = Set( [(i,round(j)) for i,j in b] )
>>> set_a.intersect ion( set_b )[/color][/color][/color]
Set([(123, 2.0), (123, 1.0), (123, 8.0)])

Or you could say ...
[color=blue][color=green][color=darkred]
>>> set_a, set_b = [[Set((i,round(j) )) for i,j in s] for s in (a,b )][/color][/color][/color]



Adam DePrince

[Adam DePrince]

Re: efficient intersection of lists with rounding

On Thu, 2004-12-02 at 22:16, Greg Ewing wrote:[color=blue]
> Gordon Williams wrote:[color=green][color=darkred]
> >>>>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)) ==[/color]
> > (l,round(m))][/color]
>
> 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 )
>[color=green]
> > - in the future I will want to round the second number of closest 0.25
> > rather than whole number.[/color]
>
> 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.
>[color=green]
> > Would the sets module be more efficient?[/color]
>
> 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.[/color]

Of course a low O-factor is important; you should avoid however
confusing the statement of what you want to do with the statement of how
you want to do it. One of the benefits of a HLL like Python is you can
merely state *what* you want without worrying about how to compute it.

In the original example above you are computing a set intersection -
python's set object has an intersection method. Use it. Not only is it
faster than your O**2 solution, but it is a good deal clearer.
[color=blue][color=green][color=darkred]
>>> from sets import Set
>>> set_a = Set( [(i,round(j)) for i,j in a] )
>>> set_b = Set( [(i,round(j)) for i,j in b] )
>>> set_a.intersect ion( set_b )[/color][/color][/color]
Set([(123, 2.0), (123, 1.0), (123, 8.0)])

Or you could say ...
[color=blue][color=green][color=darkred]
>>> set_a, set_b = [[Set((i,round(j) )) for i,j in s] for s in (a,b )][/color][/color][/color]



Adam DePrince

[Steven Bethard]

Re: efficient intersection of lists with rounding

Michael Hoffman wrote:[color=blue]
> Steven Bethard wrote:
>[color=green]
>> Well, in Python 2.3, I believe sets are implemented in Python while
>> they're implemented in C in Python 2.4.[/color]
>
> 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 ;)[/color]

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:
[color=blue]
> python -m timeit -s "a = [(123,1.3),(123, 2.4),(123,7.8), (123,10.2)];[/color]
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
[color=blue]
> python -m timeit -s "import sets; a =[/color]
[(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

[Steven Bethard]

Re: efficient intersection of lists with rounding

Michael Hoffman wrote:[color=blue]
> Steven Bethard wrote:
>[color=green]
>> Well, in Python 2.3, I believe sets are implemented in Python while
>> they're implemented in C in Python 2.4.[/color]
>
> 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 ;)[/color]

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:
[color=blue]
> python -m timeit -s "a = [(123,1.3),(123, 2.4),(123,7.8), (123,10.2)];[/color]
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
[color=blue]
> python -m timeit -s "import sets; a =[/color]
[(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

[Raymond Hettinger]

Re: efficient intersection of lists with rounding

"Gordon Williams" <g_will@cyberus .ca> wrote in message
news:mailman.70 38.1102023963.5 135.python-list@python.org ...[color=blue]
> Hi,
>
> I have to lists that I need to find the common numbers (2nd rounded to
> nearest integral) and I am wondering if there is a more efficient way of
> doing it.
>[color=green][color=darkred]
> >>> 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)) ==[/color][/color]
> (l,round(m))]
> [(123, 1.0), (123, 2.0), (123, 8.0)][color=green][color=darkred]
> >>>[/color][/color]
> This works but a and b can be in the order of 30K long.
>
> 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?[/color]

Yes:
[color=blue][color=green][color=darkred]
>>> set((x,round(y) ) for x,y in a) & set((x,round(y) ) for x,y in b)[/color][/color][/color]
set([(123, 8.0), (123, 2.0), (123, 1.0)])

[color=blue]
> I'm using python 2.3.[/color]
[color=blue][color=green][color=darkred]
>>> from sets import Set as set
>>> set([(x,round(y)) for x,y in a]) & set([(x,round(y)) for x,y in b])[/color][/color][/color]
set([(123, 8.0), (123, 2.0), (123, 1.0)])


Raymond Hettinger

[Raymond Hettinger]

Re: efficient intersection of lists with rounding

"Gordon Williams" <g_will@cyberus .ca> wrote in message
news:mailman.70 38.1102023963.5 135.python-list@python.org ...[color=blue]
> Hi,
>
> I have to lists that I need to find the common numbers (2nd rounded to
> nearest integral) and I am wondering if there is a more efficient way of
> doing it.
>[color=green][color=darkred]
> >>> 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)) ==[/color][/color]
> (l,round(m))]
> [(123, 1.0), (123, 2.0), (123, 8.0)][color=green][color=darkred]
> >>>[/color][/color]
> This works but a and b can be in the order of 30K long.
>
> 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?[/color]

Yes:
[color=blue][color=green][color=darkred]
>>> set((x,round(y) ) for x,y in a) & set((x,round(y) ) for x,y in b)[/color][/color][/color]
set([(123, 8.0), (123, 2.0), (123, 1.0)])

[color=blue]
> I'm using python 2.3.[/color]
[color=blue][color=green][color=darkred]
>>> from sets import Set as set
>>> set([(x,round(y)) for x,y in a]) & set([(x,round(y)) for x,y in b])[/color][/color][/color]
set([(123, 8.0), (123, 2.0), (123, 1.0)])


Raymond Hettinger