help with generators

Discussion in 'Python' started by Mayer, May 19, 2005.

  1. Mayer

    Mayer Guest

    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
    Mayer, May 19, 2005
    #1
    1. Advertising

  2. 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
    Steven Bethard, May 19, 2005
    #2
    1. Advertising

  3. "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
    George Sakkis, May 19, 2005
    #3
  4. Mayer

    Mayer Guest

    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, '')
    Mayer, May 19, 2005
    #4
  5. 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
    Steven Bethard, May 19, 2005
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Rhino
    Replies:
    4
    Views:
    5,652
    Roedy Green
    Jan 13, 2006
  2. Pavel

    Code Generators

    Pavel, May 14, 2006, in forum: Java
    Replies:
    7
    Views:
    708
    dimitar
    May 19, 2006
  3. Mark

    Memoizing Generators

    Mark, Jul 8, 2003, in forum: Python
    Replies:
    2
    Views:
    324
  4. Robert Brewer

    RE: Help with generators outside of loops.

    Robert Brewer, Dec 7, 2004, in forum: Python
    Replies:
    9
    Views:
    353
    David Eppstein
    Dec 8, 2004
  5. zuzu
    Replies:
    12
    Views:
    289
    Florian Gross
    Aug 27, 2004
Loading...

Share This Page