python2.4 generator expression > python2.3 list expression

Discussion in 'Python' started by snacktime, Feb 21, 2005.

  1. snacktime

    snacktime Guest

    I need to convert a generator expression to a list expression so it
    will work under python 2.3.

    I rewrote this:

    for c in range(128):
    even_odd = (sum(bool(c & 1<<b) for b in range(8))) & 1

    As this:

    for c in range(128):
    bo = [bool(c & 1<<b) for b in range(8)]
    even_odd = sum(bo) & 1


    Seems to work, is there a better way to do this?
    snacktime, Feb 21, 2005
    #1
    1. Advertising

  2. snacktime wrote:
    > I need to convert a generator expression to a list expression so it
    > will work under python 2.3.
    >
    > I rewrote this:
    >
    > for c in range(128):
    > even_odd = (sum(bool(c & 1<<b) for b in range(8))) & 1
    >
    > As this:
    >
    > for c in range(128):
    > bo = [bool(c & 1<<b) for b in range(8)]
    > even_odd = sum(bo) & 1
    >
    > Seems to work, is there a better way to do this?


    Well, if you were happy with your generator expression, you can use
    almost exactly the same syntax:

    for c in range(128):
    even_odd = (sum([bool(c & 1<<b) for b in range(8)])) & 1

    No need for the 'bo' variable...

    STeVe
    Steven Bethard, Feb 21, 2005
    #2
    1. Advertising

  3. snacktime wrote:
    > I need to convert a generator expression to a list expression so it
    > will work under python 2.3.
    >
    > I rewrote this:
    >
    > for c in range(128):
    > even_odd = (sum(bool(c & 1<<b) for b in range(8))) & 1
    >
    > As this:
    >
    > for c in range(128):
    > bo = [bool(c & 1<<b) for b in range(8)]
    > even_odd = sum(bo) & 1
    >
    >
    > Seems to work, is there a better way to do this?


    If you want to keep it as a generator that doesn't build a list
    in memory, you can use itertools:

    import itertools

    for c in range(128):
    def _even_odd_func(b): return bool(c & 1<<b)
    even_odd = (sum(itertools.imap(_even_odd_func, xrange(8)))) & 1

    The fact that you used range() instead of xrange() indicates that
    you may not care about this, though. ;-)
    --
    Michael Hoffman
    Michael Hoffman, Feb 21, 2005
    #3
  4. snacktime

    Peter Otten Guest

    snacktime wrote:

    > I need to convert a generator expression to a list expression so it
    > will work under python 2.3.
    >
    > I rewrote this:
    >
    > for c in range(128):
    > even_odd = (sum(bool(c & 1<<b) for b in range(8))) & 1
    >
    > As this:
    >
    > for c in range(128):
    > bo = [bool(c & 1<<b) for b in range(8)]
    > even_odd = sum(bo) & 1
    >
    >
    > Seems to work, is there a better way to do this?


    Summing over zeros seems pointless, so

    >>> for c in range(128):

    .... print len([1 for b in range(8) if c & 1 << b]) & 1,
    ....
    0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1
    1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0
    1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0
    0 1 0 1 1 0 0 1 1 0 1 0 0 1

    The same simplification works for genexps, but you have to use sum() there
    instead of len(). Another optimization would be to precalculate the
    bitmasks [1 << b for b in range(8)] outside the loop.

    Peter
    Peter Otten, Feb 21, 2005
    #4
  5. snacktime

    Dan Sommers Guest

    On Sun, 20 Feb 2005 20:56:52 -0800,
    snacktime <> wrote:

    > I need to convert a generator expression to a list expression so it
    > will work under python 2.3.


    > I rewrote this:


    > for c in range(128):
    > even_odd = (sum(bool(c & 1<<b) for b in range(8))) & 1


    > As this:


    > for c in range(128):
    > bo = [bool(c & 1<<b) for b in range(8)]
    > even_odd = sum(bo) & 1



    > Seems to work, is there a better way to do this?


    for c in range( 128 ):
    even_odd = 0
    print '%3d' % c,
    while c:
    c &= c - 1
    even_odd = not even_odd
    print int( even_odd )

    Okay, so your inner loop is only counting to 8, but IMO this is a good
    example of how to use a better algorithm instead of optimizing the code
    of a naïve one. My inner loop only iterates over 1-bits.

    "Better," of course is all relative. Your algorithm obviously counts
    bits in an integer. My algorithm is less clear at first glance (and
    even second and third glance), but nearly idiomatic to those of us who
    spent lots of time writing embedded assembly code.

    If you have the space to spare, a lookup table (pre-calculated or
    created during your program's initialization) is probably the best way
    to go.

    Regards,
    Dan

    --
    Dan Sommers
    <http://www.tombstonezero.net/dan/>
    Never play leapfrog with a unicorn.
    Dan Sommers, Feb 21, 2005
    #5
  6. On 21 Feb 2005 06:48:19 -0500, rumours say that Dan Sommers <>
    might have written:

    [snip: snacktime posts code to count bits]

    >> Seems to work, is there a better way to do this?


    [Dan]
    >for c in range( 128 ):
    > even_odd = 0
    > print '%3d' % c,
    > while c:
    > c &= c - 1
    > even_odd = not even_odd
    > print int( even_odd )


    Just for the sake of people who haven't messed with bit manipulation in C or
    assembly, the effect of

    c &= c - 1

    is to reset the rightmost (less significant) '1' bit of a number (ie change it
    to '0').
    --
    TZOTZIOY, I speak England very best.
    "Be strict when sending and tolerant when receiving." (from RFC1958)
    I really should keep that in mind when talking with people, actually...
    Christos TZOTZIOY Georgiou, Feb 21, 2005
    #6
  7. snacktime

    Bryan Guest

    Christos TZOTZIOY Georgiou wrote:
    > On 21 Feb 2005 06:48:19 -0500, rumours say that Dan Sommers <>
    > might have written:
    >
    > [snip: snacktime posts code to count bits]
    >
    >
    >>>Seems to work, is there a better way to do this?

    >
    >
    > [Dan]
    >
    >>for c in range( 128 ):
    >> even_odd = 0
    >> print '%3d' % c,
    >> while c:
    >> c &= c - 1
    >> even_odd = not even_odd
    >> print int( even_odd )

    >
    >
    > Just for the sake of people who haven't messed with bit manipulation in C or
    > assembly, the effect of
    >
    > c &= c - 1
    >
    > is to reset the rightmost (less significant) '1' bit of a number (ie change it
    > to '0').


    i tried c &= c - 1 but i'm not getting the least significant or rightmost bit
    reset to zero. am i misunderstanding something?

    >>> 2 & 1 # 2 = 0x10; reset right most would be 0x10

    0
    >>> 10 & 9 # 10 = 0x1010; reset right most would be 0x1010

    8

    bryan
    Bryan, Feb 21, 2005
    #7
  8. snacktime

    Duncan Booth Guest

    Bryan wrote:

    >> is to reset the rightmost (less significant) '1' bit of a number (ie
    >> change it to '0').

    >
    > i tried c &= c - 1 but i'm not getting the least significant or
    > rightmost bit reset to zero. am i misunderstanding something?
    >
    > >>> 2 & 1 # 2 = 0x10; reset right most would be 0x10

    > 0
    > >>> 10 & 9 # 10 = 0x1010; reset right most would be 0x1010

    > 8


    The difference between the original "reset the rightmost '1' bit", and your
    interpretation: "reset the rightmost bit" is the "'1'".

    The rightmost bit that is set is reset. So 0x10 -> 0, and 0x1010 -> 0x1000.

    If you want to extract the least significant set bit from a number 'x' you
    can use (x&-x):

    >>> x = 0xab4
    >>> while x:

    print hex(x&-x), hex(x)
    x ^= (x&-x)


    0x4 0xab4
    0x10 0xab0
    0x20 0xaa0
    0x80 0xa80
    0x200 0xa00
    0x800 0x800
    >>>


    (but don't try this if x is negative: it works but never terminates).
    Duncan Booth, Feb 21, 2005
    #8
  9. snacktime

    Brian Beck Guest

    Duncan Booth wrote:
    > The difference between the original "reset the rightmost '1' bit", and your
    > interpretation: "reset the rightmost bit" is the "'1'".
    >
    > The rightmost bit that is set is reset. So 0x10 -> 0, and 0x1010 -> 0x1000.
    >
    > If you want to extract the least significant set bit from a number 'x' you
    > can use (x&-x):


    My interpretation of Bryan's (mis?)interpretation (heh) was that since
    in the numbers 2 and 10 (as in his examples), the least significant bit
    was already 0, performing an operation that set it to 0 should result in
    the number unchanged. As his tests show, this is not the case. This is
    because the operation works only if the least significant bit actually
    NEEDS to be unset. To zero the least significant bit unconditionally, we
    can use:

    x &= ~1

    --
    Brian Beck
    Adventurer of the First Order
    Brian Beck, Feb 21, 2005
    #9
  10. snacktime

    Bryan Guest

    Duncan Booth wrote:
    > Bryan wrote:
    >
    >
    >>>is to reset the rightmost (less significant) '1' bit of a number (ie
    >>>change it to '0').

    >>
    >>i tried c &= c - 1 but i'm not getting the least significant or
    >>rightmost bit reset to zero. am i misunderstanding something?
    >>
    >>
    >>>>>2 & 1 # 2 = 0x10; reset right most would be 0x10

    >>
    >>0
    >>
    >>>>>10 & 9 # 10 = 0x1010; reset right most would be 0x1010

    >>
    >>8

    >
    >
    > The difference between the original "reset the rightmost '1' bit", and your
    > interpretation: "reset the rightmost bit" is the "'1'".
    >
    > The rightmost bit that is set is reset. So 0x10 -> 0, and 0x1010 -> 0x1000.
    >
    > If you want to extract the least significant set bit from a number 'x' you
    > can use (x&-x):
    >
    >
    >>>>x = 0xab4
    >>>>while x:

    >
    > print hex(x&-x), hex(x)
    > x ^= (x&-x)
    >
    >
    > 0x4 0xab4
    > 0x10 0xab0
    > 0x20 0xaa0
    > 0x80 0xa80
    > 0x200 0xa00
    > 0x800 0x800
    >
    >
    > (but don't try this if x is negative: it works but never terminates).


    thanks duncan... you're right, i did intrepret this as "reset the rightmost bit"
    instead of "reset the rightmost '1' bit". and i must have read what christos
    wrote 100 times!!!

    bryan
    Bryan, Feb 21, 2005
    #10
  11. snacktime

    Terry Reedy Guest

    "Christos TZOTZIOY Georgiou" <> wrote in message
    news:...
    > On 21 Feb 2005 06:48:19 -0500, rumours say that Dan Sommers
    > <>
    >>for c in range( 128 ):
    >> even_odd = 0
    >> print '%3d' % c,
    >> while c:
    >> c &= c - 1
    >> even_odd = not even_odd
    >> print int( even_odd )

    >
    > Just for the sake of people who haven't messed with bit manipulation in C
    > or
    > assembly, the effect of
    > c &= c - 1
    > is to reset the rightmost (less significant) '1' bit of a number (ie
    > change it
    > to '0').


    Cute. I tried it a few times until I saw why it works. But it is also
    dangerous (within a loop like the above) in a language like current Python
    (and unlike C/assembler) in which the binary representation of -1 is
    effectively a left infinite string of '1's: ...1111111111

    Terry J. Reedy
    Terry Reedy, Feb 21, 2005
    #11
  12. On Mon, 21 Feb 2005 10:55:05 -0800, rumours say that Bryan <>
    might have written:



    >>>>is to reset the rightmost (less significant) '1' bit of a number (ie
    >>>>change it to '0').


    [bryan]
    >>>i tried c &= c - 1 but i'm not getting the least significant or
    >>>rightmost bit reset to zero. am i misunderstanding something?
    >>>
    >>>
    >>>>>>2 & 1 # 2 = 0x10; reset right most would be 0x10


    <snip>

    [Duncan]
    >> The difference between the original "reset the rightmost '1' bit", and your
    >> interpretation: "reset the rightmost bit" is the "'1'".
    >>
    >> The rightmost bit that is set is reset. So 0x10 -> 0, and 0x1010 -> 0x1000.


    <snip>


    >thanks duncan... you're right, i did intrepret this as "reset the rightmost bit"
    >instead of "reset the rightmost '1' bit". and i must have read what christos
    >wrote 100 times!!!


    Don't worry, Bryan, I'm probably more to blame, since I have this tendency to
    interject parenthesized sub-sentences all over my paragraphs, that probably
    confuse more than clarify things ( self.remind(prose is not code) :).

    Perhaps I should crosspost my replies (esp. the ones with nested parentheses) to
    comp.lang.lisp ...
    --
    TZOTZIOY, I speak England very best.
    "Be strict when sending and tolerant when receiving." (from RFC1958)
    I really should keep that in mind when talking with people, actually...
    Christos TZOTZIOY Georgiou, Feb 22, 2005
    #12
  13. snacktime

    Duncan Booth Guest

    Dan Sommers wrote:

    >> Seems to work, is there a better way to do this?

    >
    > for c in range( 128 ):
    > even_odd = 0
    > print '%3d' % c,
    > while c:
    > c &= c - 1
    > even_odd = not even_odd
    > print int( even_odd )
    >
    > Okay, so your inner loop is only counting to 8, but IMO this is a good
    > example of how to use a better algorithm instead of optimizing the code
    > of a naïve one. My inner loop only iterates over 1-bits.
    >


    Here's yet another way to achieve the same results. This version doesn't
    iterate over any bits at all:

    >>> import operator
    >>> parity = [ False ]
    >>> for i in range(7):

    parity += map(operator.not_, parity)

    And if you want the same output:

    >>> for even_odd in parity:

    print int(even_odd)
    Duncan Booth, Feb 22, 2005
    #13
  14. snacktime

    Dan Sommers Guest

    On 22 Feb 2005 09:14:50 GMT,
    Duncan Booth <> wrote:

    > Here's yet another way to achieve the same results. This version doesn't
    > iterate over any bits at all:


    >>>> import operator
    >>>> parity = [ False ]
    >>>> for i in range(7):

    > parity += map(operator.not_, parity)


    Very clever! :)

    Picking a nit, that version iterates over *two* sets of bits. The "for"
    loop over each possible bit in the input values. The "map" function
    over the parity bits accumulated up to that point. And the "+="
    operator over those same bits again. Make that *three* sets of bits.

    I stand humbled.

    Regards,
    Dan

    --
    Dan Sommers
    <http://www.tombstonezero.net/dan/>
    μ₀ × ε₀ × c² = 1
    Dan Sommers, Feb 22, 2005
    #14
    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. Xavier
    Replies:
    0
    Views:
    418
    Xavier
    Aug 6, 2003
  2. Skip Montanaro
    Replies:
    1
    Views:
    434
    Thomas Heller
    Aug 7, 2003
  3. Uwe Mayer

    changing from python2.3 to python2.4

    Uwe Mayer, Apr 8, 2005, in forum: Python
    Replies:
    1
    Views:
    302
    =?ISO-8859-1?Q?=22Martin_v=2E_L=F6wis=22?=
    Apr 9, 2005
  4. Replies:
    9
    Views:
    539
  5. Ksenia Marasanova
    Replies:
    2
    Views:
    355
    Mike Meyer
    Nov 17, 2005
Loading...

Share This Page