Velocity Reviews > help with generators

# help with generators

Mayer
Guest
Posts: n/a

 05-19-2005
Hello:

I need some help in understanding generators. I get them to work in
simple cases, but the following example puzzles me. Consider the
non-generator, "ordinary" procedure:

def foo(n):
s = []
def foo(n):
if n == 0:
print s
else:
s.append(0)
foo(n - 1)
s.pop()
s.append(1)
foo(n - 1)
s.pop()
foo(n)

foo(n) prints all n-bit-wide binary numbers as a list. I would now like
to create a generator for such numbers:

def bin(n):
s = []
def bin(n):
if n == 0:
yield s
else:
s.append(0)
bin(n - 1)
s.pop()
s.append(1)
bin(n - 1)
s.pop()
return bin(n)

yet this doesn't work as expected. Can someone please explain why?

Thanks,

Mayer Goldberg

Steven Bethard
Guest
Posts: n/a

 05-19-2005
Mayer wrote:
> Hello:
>
> I need some help in understanding generators. I get them to work in
> simple cases, but the following example puzzles me. Consider the
> non-generator, "ordinary" procedure:
>
> def foo(n):
> s = []
> def foo(n):
> if n == 0:
> print s
> else:
> s.append(0)
> foo(n - 1)
> s.pop()
> s.append(1)
> foo(n - 1)
> s.pop()
> foo(n)
>
> foo(n) prints all n-bit-wide binary numbers as a list. I would now like
> to create a generator for such numbers:
>
> def bin(n):
> s = []
> def bin(n):
> if n == 0:
> yield s
> else:
> s.append(0)
> bin(n - 1)
> s.pop()
> s.append(1)
> bin(n - 1)
> s.pop()
> return bin(n)
>
> yet this doesn't work as expected. Can someone please explain why?

It would help if you explained what you expected. But here's code that

py> def bin(n):
.... s = []
.... def bin(n):
.... if n == 0:
.... yield s
.... else:
.... s.append(0)
.... for s1 in bin(n - 1):
.... yield s1
.... s.pop()
.... s.append(1)
.... for s1 in bin(n - 1):
.... yield s1
.... s.pop()
.... return bin(n)
....
py> for s in bin(1):
.... print s
....
[0]
[1]
py> for s in bin(2):
.... print s
....
[0, 0]
[0, 1]
[1, 0]
[1, 1]

Note that to make the recursive calls work, you *must* iterate through
them, thus what was in your code:

bin(n - 1)

now looks like:

for s1 in bin(n - 1):
yield s1

This is crucial. bin(n - 1) creates a generator object. But unless you
put it in a for-loop (or call it's .next()) method, the generator will
never execute any code.

HTH,

STeVe

George Sakkis
Guest
Posts: n/a

 05-19-2005
"Steven Bethard" wrote:

> It would help if you explained what you expected. But here's code

that
>
> py> def bin(n):
> ... s = []
> ... def bin(n):
> ... if n == 0:
> ... yield s
> ... else:
> ... s.append(0)
> ... for s1 in bin(n - 1):
> ... yield s1
> ... s.pop()
> ... s.append(1)
> ... for s1 in bin(n - 1):
> ... yield s1
> ... s.pop()
> ... return bin(n)
> ...
> py> for s in bin(1):
> ... print s
> ...
> [0]
> [1]
> py> for s in bin(2):
> ... print s
> ...
> [0, 0]
> [0, 1]
> [1, 0]
> [1, 1]
>
> Note that to make the recursive calls work, you *must* iterate

through
> them, thus what was in your code:
>
> bin(n - 1)
>
> now looks like:
>
> for s1 in bin(n - 1):
> yield s1
>
> This is crucial. bin(n - 1) creates a generator object. But unless

you
> put it in a for-loop (or call it's .next()) method, the generator

will
> never execute any code.
>
> HTH,
>
> STeVe

A caveat of the implementation above: it yields the same instance (s),
which is unsafe if the loop variable is modified (e.g. in the "for s in
bin(n)" loop, s should not be modified). Moreover, each yielded value
should be 'consumed' and then discarded; attempting to store it (as in
list(bin(n))) references only the last yielded value.

Here's a shorter, clear and safe implementation:

def bin2(n):
if n:
for tail in bin2(n-1):
yield [0] + tail
yield [1] + tail
else:
yield []

It also turns out to be faster than the original despite yielding a new
list every time:
\$ python /usr/local/lib/python2.4/timeit.py -s "from bin import bin"
"for i in bin(10): pass"
100 loops, best of 3: 5.21 msec per loop
\$ python /usr/local/lib/python2.4/timeit.py -s "from bin import bin2"
"for i in bin2(10): pass"
100 loops, best of 3: 2.68 msec per loop

The reason is that the original computes the same permutations ("for s1
in bin(n - 1)") twice. Here's a faster version that preallocates the
list and sets the 0s and 1s for each permutation:

def bin3(n):
array = [None]*n
def _bin(n):
if not n:
yield array
else:
n -= 1
for perm in _bin(n):
# replace 'yield perm' with 'yield list(perm)' for safe
# mutation and accumulation of yielded lists
perm[n] = 0; yield perm
perm[n] = 1; yield perm
return _bin(n)

\$ python /usr/local/lib/python2.4/timeit.py -s "from bin import bin3"
"for i in bin3(10): pass"
1000 loops, best of 3: 587 usec per loop

Cheers,
George

Mayer
Guest
Posts: n/a

 05-19-2005
Thanks a lot! This clarified [I think] my misunderstanding about yield,
and I also learned something about efficiency from George's code --
Thanks.

So, The function tel(aString) takes a string (or a number) that denote
a phone number, using digits or letters, and returns a generator for
the set of all possible words that are made up of that phone number.
It's not a terribly useful program, but it's short and it's a lot of
fun.

Mayer

import string

for ch in keyString:

def tel(phone):
phoneString = str(phone)
length = len(phoneString)
buffer = [Null] * length
def run(n):
if n == length:
yield string.join(buffer, '')
else:
for word in run(n + 1):
buffer[n] = letter
yield buffer
return run(0, '')

Steven Bethard
Guest
Posts: n/a

 05-19-2005
George Sakkis wrote:
> "Steven Bethard" wrote:
>
>>py> def bin(n):
>>... s = []
>>... def bin(n):
>>... if n == 0:
>>... yield s
>>... else:
>>... s.append(0)
>>... for s1 in bin(n - 1):
>>... yield s1
>>... s.pop()
>>... s.append(1)
>>... for s1 in bin(n - 1):
>>... yield s1
>>... s.pop()
>>... return bin(n)
>>...

[snip]
> A caveat of the implementation above: it yields the same instance (s),
> which is unsafe if the loop variable is modified (e.g. in the "for s in
> bin(n)" loop, s should not be modified). Moreover, each yielded value
> should be 'consumed' and then discarded; attempting to store it (as in
> list(bin(n))) references only the last yielded value.

Yup. However, this was the most direct translation of the OP's original
function (which also only had a single list). Since the question was
about how generators worked, I figured the most direct translation would
probably be the most useful response.

> Here's a shorter, clear and safe implementation:
>
> def bin2(n):
> if n:
> for tail in bin2(n-1):
> yield [0] + tail
> yield [1] + tail
> else:
> yield []

This is definitely the way I would have written it.

STeVe