# PEP 255: Simple Generators

Tim Peters tim.one at home.com
Mon Jun 25 00:39:40 CEST 2001

```[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, 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, 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)

```