python2.4 generator expression > python2.3 list expression

S

snacktime

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?
 
S

Steven Bethard

snacktime said:
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
 
M

Michael Hoffman

snacktime said:
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. ;-)
 
P

Peter Otten

snacktime said:
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
.... 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
 
D

Dan Sommers

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
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
 
C

Christos TZOTZIOY Georgiou

On 21 Feb 2005 06:48:19 -0500, rumours say that Dan Sommers <[email protected]>
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').
 
B

Bryan

Christos said:
On 21 Feb 2005 06:48:19 -0500, rumours say that Dan Sommers <[email protected]>
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?
8

bryan
 
D

Duncan Booth

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

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):
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).
 
B

Brian Beck

Duncan said:
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
 
B

Bryan

Duncan said:
Bryan 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):



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
 
T

Terry Reedy

Christos TZOTZIOY Georgiou said:
On 21 Feb 2005 06:48:19 -0500, rumours say that Dan Sommers


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
 
C

Christos TZOTZIOY Georgiou

[bryan]<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.

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 ...
 
D

Duncan Booth

Dan said:
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:
print int(even_odd)
 
D

Dan Sommers

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,733
Messages
2,569,440
Members
44,832
Latest member
GlennSmall

Latest Threads

Top