Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > help with generators

Reply
Thread Tools

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

 
Reply With Quote
 
 
 
 
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
prints about the same as your non-generator function.

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
 
Reply With Quote
 
 
 
 
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
> prints about the same as your non-generator function.
>
> 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

 
Reply With Quote
 
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

def addKeyString(keyString):
for ch in keyString:
keypad[ch] = keyString

keypad = {}
addKeyString('0')
addKeyString('1')
addKeyString('2ABC')
addKeyString('3DEF')
addKeyString('4GHI')
addKeyString('5JKL')
addKeyString('6MNO')
addKeyString('7PQRS')
addKeyString('8TUV')
addKeyString('9WXYZ')

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):
for letter in keypad[phoneString[n]]:
buffer[n] = letter
yield buffer
return run(0, '')

 
Reply With Quote
 
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Code Generators Pavel Java 7 05-19-2006 04:21 PM
JUnit question: testing file generators Rhino Java 4 01-13-2006 02:15 AM
RE: Help with generators outside of loops. Robert Brewer Python 9 12-08-2004 07:14 PM
python generators to ruby closures, help zuzu Ruby 12 08-27-2004 10:17 PM
Memoizing Generators Mark Python 2 07-09-2003 02:19 PM



Advertisments