[Tutor] Double loop and performances
Kent Johnson
kent37 at tds.net
Tue Jun 7 15:59:11 CEST 2005
Benjamin Klein-Fignier wrote:
> Hi,
>
> I am wondering if there is a way to efficiently run a double loop in
> Python. To be more precise, I would like to compute the sum of a
> function f(x,y) for every possible (x,y) pair.
How big are your lists (X and Y)?
A few minor suggestions below.
> I have tried several alternatives so far:
>
> 1) the classic double loop:
> for x in X:
> for y in Y:
> sum += f(x,y)
>
> 2) using list comprehension:
> sum([f(x,y) for x in X for y in Y])
In Python 2.4 you can write the above with a generator expression which may be faster and will certainly use less memory:
sum(f(x,y) for x in X for y in Y)
> 3) I figured out that the loop was slow, so I used map() to generate
> a list of every combination and then map to compute the result. But
> it is not very memory efficient and still pretty slow.
Try using itertools.imap() instead of map(), it will cut down the memory use (though the result is not the same as map() if the lists passed to it are different lengths).
If this is done inside a function, bind f to a local variable, that speeds lookup.
This thread in comp.lang.python is interesting though it solves a more general problem and it is old so its results may no longer be valid:
http://groups-beta.google.com/group/comp.lang.python/browse_frm/thread/de552741a17378bc/bb02de365f85e916?q=p13x25&rnum=1&hl=en#bb02de365f85e916
Here is one solution from that thread modified to work with just two lists:
def permute(X, Y):
import operator
result = map(lambda I: (I,), X)
curr = []
for item in Y:
new = map(operator.add, result, [(item,)]*len(result))
curr[len(curr):] = new
result = curr
return result
though it's hard to believe that will be faster than just ((x,y) for x in X for y in Y)
Leaving the actual testing to you,
Kent
More information about the Tutor
mailing list