Anton Vredegoor <[EMAIL PROTECTED]> writes:
> I want the product, but sorted in less time. If Fourier transforms can
> help, I want them :-)
Oh, I see what you mean. I don't see an obvious faster way to do it
and I don't have the feeling that one necessarily exists. As someone
mentioned, you could do an n-way merge, which at least avoids using
quadratic memory. Here's a version using Frederik Lundh's trick of
representing a lazy list as its head plus the generator for the tail:
from heapq import heapify, heappop, heappush
import random
def sortedsums(L,R):
# yield elements of [(i+j) for i in L for j in R] in sorted order
# assumes L and R are themselves sorted
def lundh(x):
g = ((a+x) for a in L)
return (g.next(), g)
heap = [lundh(x) for x in R]
heapify (heap) # not sure this is needed
while heap:
z,zn = heappop(heap)
try: heappush(heap, (zn.next(), zn))
except StopIteration: pass
yield z
def test():
L = sorted(random.sample(xrange(2000),150))
R = sorted(random.sample(xrange(2000),150))
t = sortedsums(L,R)
t2 = sorted([(i+j) for i in L for j in R])
assert list(t) == t2
test()
--
http://mail.python.org/mailman/listinfo/python-list
