PEP 255: Simple Generators

[Tim Peters]

[Roman Suzi, on my gcomb example]
> This implementation is cool, but how fast will be recursive generators?
> How large is the overhead to defrost execution frame each time? Will it
> be faster than functional gcomb?

The high-order bit is that I couldn't care less:  you can do generator
implementations "like this" in your sleep once you're used to the idea, and
it's extremely convenient -- meaning it's the least burden on *my* time to
get from idea to working implementation.  But if you're dead serious about
machine time in Python, you don't use recursion of any flavor.

That said, I'll attach a complete timing program below.  Note that the
structures of the generator and recursive versions are almost exactly the
same.  This isn't an accident:  a "gather the elements into a giant list"
algorithm can usually be transformed into a one-at-a-time generator very
easily just by replacing the appends with yields, and a return of an empty
list by stopping the generator (a raw "return").

On my box at the moment (Win98SE), the generator version below-- and on the
test case shown --is about a 50% speedup over the recursive version (about
.16 seconds for gcomb and .24 for rcomb).

less-filling-and-tastes-great-ly y'rs  - tim

PS:  In rcomb, a good speedup can be obtained by replacing

        for c in rcomb(rest, k):
            result.append(c)
by
        result.extend(rcomb(rest, k))

Then gcomb's speed advantage fell to about 25%.  But rcomb still has to
materialize the memory for 3,432 7-element lists in one gulp, while gcomb's
memory use is minimal.


def gcomb(x, k):
    "Generate all combinations of k elements from list x."
    if k > len(x):
        return
    if k == 0:
        yield []
    else:
        first, rest = x[0], x[1:]
        # A combination does or doesn't contain first.
        # If it does, the remainder is a k-1 comb of rest.
        for c in gcomb(rest, k-1):
            c.insert(0, first)
            yield c
        # If it doesn't contain first, it's a k comb of rest.
        for c in gcomb(rest, k):
            yield c

def rcomb(x, k):
    "Return list of all combinations of k elements from list x."
    result = []
    if k > len(x):
        return result
    if k == 0:
        result.append([])
    else:
        first, rest = x[0], x[1:]
        # A combination does or doesn't contain first.
        # If it does, the remainder is a k-1 comb of rest.
        for c in rcomb(rest, k-1):
            c.insert(0, first)
            result.append(c)
        # If it doesn't contain first, it's a k comb of rest.
        for c in rcomb(rest, k):
            result.append(c)
    return result

seq = range(1, 5)

print "Sanity check for generator:"
for c in gcomb(seq, 2):
    print c
print

print "Sanity check for recursive version:"
for c in rcomb(seq, 2):
    print c
print


def timer(f, seq, k):
    from time import clock
    count = 0
    start = clock()
    for x in f(seq, k):
        count += 1
    finish = clock()
    return count, finish - start

N = 14
seq = range(N)
k = N / 2

print "Timing gcomb and rcomb on %d-combs of a %d-element list:" % (k, N)
for trial in range(5):
    for func in gcomb, rcomb:
        count, time = timer(func, seq, len(seq)/2)
        print "    %s returned %d results in %.3f seconds" % (
            func.__name__, count, time)