[Tutor] Double loop and performances

[Kent Johnson]

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