Hpw make lists that are easy to sort.

[Paul Rubin]

Anton Vredegoor <anton.vredegoor at gmail.com> 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()