Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #32131 > unrolled thread

bit count or bit set && Python3

Back to article view | Back to comp.lang.python

Contents

  bit count or bit set && Python3 Charles Hixson <charleshixsn@earthlink.net> - 2012-10-25 07:47 -0700
    Re: bit count or bit set && Python3 rusi <rustompmody@gmail.com> - 2012-10-25 09:13 -0700
      Re: bit count or bit set && Python3 Terry Reedy <tjreedy@udel.edu> - 2012-10-25 16:16 -0400
    Re: bit count or bit set && Python3 Christian Gollwitzer <auriocus@gmx.de> - 2012-10-25 19:25 +0200
      Re: bit count or bit set && Python3 Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-25 12:19 -0600
    Re: bit count or bit set && Python3 casevh@gmail.com - 2012-10-26 08:42 -0700
      Re: bit count or bit set && Python3 Charles Hixson <charleshixsn@earthlink.net> - 2012-10-26 09:30 -0700
    Re: bit count or bit set && Python3 casevh@gmail.com - 2012-10-26 08:42 -0700

#32131 — bit count or bit set && Python3

In Python3 is there any good way to count the number of on bits in an 
integer (after an & operation)?
Alternatively, is there any VERY light-weight implementation of a bit 
set?  I'd prefer to use integers, as I'm probably going to need 
thousands of these, if the tests work out.  But before I can test, I 
need a decent bit counter.  (shift, xor, &, and | are already present 
for integer values, but I also need to count the number of "true" items 
after the logical operation.  So if a bitset is the correct approach, 
I'll need it to implement those operations, or their equivalents in 
terms of union and intersection.)

Or do I need to drop into C for this?

-- 
Charles Hixson

[toc] | [next] | [standalone]

#32139

On Oct 25, 7:56 pm, Charles Hixson <charleshi...@earthlink.net> wrote:
> In Python3 is there any good way to count the number of on bits in an
> integer (after an & operation)?
> Alternatively, is there any VERY light-weight implementation of a bit
> set?  I'd prefer to use integers, as I'm probably going to need
> thousands of these, if the tests work out.  But before I can test, I
> need a decent bit counter.  (shift, xor, &, and | are already present
> for integer values, but I also need to count the number of "true" items
> after the logical operation.  So if a bitset is the correct approach,
> I'll need it to implement those operations, or their equivalents in
> terms of union and intersection.)
>
> Or do I need to drop into C for this?
>
> --
> Charles Hixson

You may have already checked it out and find it unsuitable...
I guess you know that python has good implementation of sets
http://docs.python.org/library/sets.html ?

[toc] | [prev] | [next] | [standalone]

#32159

On 10/25/2012 12:13 PM, rusi wrote:
> On Oct 25, 7:56 pm, Charles Hixson <charleshi...@earthlink.net> wrote:
>> In Python3 is there any good way to count the number of on bits in an
>> integer (after an & operation)?
>> Alternatively, is there any VERY light-weight implementation of a bit
>> set?  I'd prefer to use integers, as I'm probably going to need
>> thousands of these, if the tests work out.  But before I can test, I
>> need a decent bit counter.  (shift, xor, &, and | are already present
>> for integer values, but I also need to count the number of "true" items
>> after the logical operation.  So if a bitset is the correct approach,
>> I'll need it to implement those operations, or their equivalents in
>> terms of union and intersection.)
>>
>> Or do I need to drop into C for this?

If I wanted 1000s of fast limited-length bitsets, I would consider using 
Cython to make an extension class.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#32151

Am 25.10.12 16:47, schrieb Charles Hixson:
> In Python3 is there any good way to count the number of on bits in an
> integer (after an & operation)?
> Alternatively, is there any VERY light-weight implementation of a bit
> set?  I'd prefer to use integers, as I'm probably going to need
> thousands of these, if the tests work out.  But before I can test, I
> need a decent bit counter.  (shift, xor, &, and | are already present
> for integer values, but I also need to count the number of "true" items
> after the logical operation.  So if a bitset is the correct approach,
> I'll need it to implement those operations, or their equivalents in
> terms of union and intersection.)
>
> Or do I need to drop into C for this?
>

There is a very geeky algorithm with only a few integer operations.

Checkout
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSet64

for a C version. Maybe the same thing is equally fast when ported to 
Python.

	Christian

[toc] | [prev] | [next] | [standalone]

#32153

On Thu, Oct 25, 2012 at 11:25 AM, Christian Gollwitzer <auriocus@gmx.de> wrote:
> There is a very geeky algorithm with only a few integer operations.
>
> Checkout
> http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSet64
>
> for a C version. Maybe the same thing is equally fast when ported to Python.

It does seem to be about five times faster than the loop, but still
only half as fast as the string-counting approach.  I'm using a 64-bit
CPU but only a 32-bit OS, but it probably doesn't make much difference
anyway for Python, which is going to do the computations with Python
longs rather than with 64-bit C integers.

Also, this approach is a bit limited in that it only works for 32-bit
ints, so you can't pass it an aribtrary precision int and expect
correct results.

By the way, I expect the reason that Steve saw a 600x difference and
I'm only getting a 10x difference is because he was testing 10000-bit
ints with expensive "long" operations, whereas I'm using 32-bit ints
that aren't too far removed from the C level.


>>> from timeit import Timer
>>> t = Timer("bin(number).count('1')", setup="number=2**31-1")
>>> min(t.repeat(number=1000000, repeat=7))
0.6388884620810749
>>> def count_set_bits(number):
...   count = 0
...   while number:
...     count += 1
...     number &= number - 1
...   return count
...
>>> t = Timer("count_set_bits(number)", setup="from __main__ import count_set_bi
ts; number = 2 ** 31-1")
>>> min(t.repeat(number=100000, repeat=7))
0.5898140685478239
>>> def count_set_bits_geeky(number):
...     c = ((number & 0xfff) * 0x1001001001001 & 0x84210842108421) % 0x1f
...     c += (((number & 0xfff000) >> 12) * 0x1001001001001 & 0x84210842108421)
% 0x1f
...     c += ((number >> 24) * 0x1001001001001 & 0x84210842108421) % 0x1f
...     return c
...
>>> t = Timer("count_set_bits_geeky(number)", setup="from __main__ import count_
set_bits_geeky; number = 2 ** 31-1")
>>> min(t.repeat(number=100000, repeat=7))
0.1247119396459766

[toc] | [prev] | [next] | [standalone]

#32219

On Thursday, October 25, 2012 7:56:25 AM UTC-7, Charles Hixson wrote:
> In Python3 is there any good way to count the number of on bits in an 
> integer (after an & operation)?

You may want to look at gmpy2[1] and the popcount() function.

> 
> Alternatively, is there any VERY light-weight implementation of a bit 
> set?  I'd prefer to use integers, as I'm probably going to need 
> thousands of these, if the tests work out.  But before I can test, I 
> need a decent bit counter.  (shift, xor, &, and | are already present 
> for integer values, but I also need to count the number of "true" items 
> after the logical operation.  So if a bitset is the correct approach, 
> 

Whether or not gmpy2 is considered light-weight is debateable. :)

> I'll need it to implement those operations, or their equivalents in 
> terms of union and intersection.)
> 
> 
> 
> Or do I need to drop into C for this?
> 

[1] http://code.google.com/p/gmpy/

> 
> 
> -- 
> 
> Charles Hixson

[toc] | [prev] | [next] | [standalone]

#32225

casevh@gmail.com wrote:
> On Thursday, October 25, 2012 7:56:25 AM UTC-7, Charles Hixson wrote:
>> In Python3 is there any good way to count the number of on bits in an
>> integer (after an&  operation)?
> You may want to look at gmpy2[1] and the popcount() function.
>
>> Alternatively, is there any VERY light-weight implementation of a bit
>> set?  I'd prefer to use integers, as I'm probably going to need
>> thousands of these, if the tests work out.  But before I can test, I
>> need a decent bit counter.  (shift, xor,&, and | are already present
>> for integer values, but I also need to count the number of "true" items
>> after the logical operation.  So if a bitset is the correct approach,
>>
> Whether or not gmpy2 is considered light-weight is debateable. :)
>
>> I'll need it to implement those operations, or their equivalents in
>> terms of union and intersection.)
>>
>>
>>
>> Or do I need to drop into C for this?
>>
> [1] http://code.google.com/p/gmpy/
>
>>
>> -- 
>>
>> Charles Hixson
I can see many times when that would be useful, but for this particular 
case I think that bin(val).count("1") is probably the better solution.  
The other options that I need are already available directly in integer 
numbers, and I will be surprised if I need more than a 32-bit set, so 
integers should be a reasonable approach.  It doesn't seem to have the 
overhead that I feared a string conversion would have (possibly because 
converting an integer to a bit string is trivial),  so I don't think 
that gmpy would add value to this program.

Next I need to decide about weak pointers, and then shelve vs. 
tokyocabinet.  (I sort of don't like shelve, because of its use of 
pickle, with the attendent security risks.  OTOH, the file will be local 
to the computer, not going over the net, which minimizes that.  Still, I 
may decide to reimplement it using ast.literal_eval, as I'm not 
intending to store anything that it won't handle.

[toc] | [prev] | [next] | [standalone]

#32221

On Thursday, October 25, 2012 7:56:25 AM UTC-7, Charles Hixson wrote:
> In Python3 is there any good way to count the number of on bits in an 
> integer (after an & operation)?

You may want to look at gmpy2[1] and the popcount() function.

> 
> Alternatively, is there any VERY light-weight implementation of a bit 
> set?  I'd prefer to use integers, as I'm probably going to need 
> thousands of these, if the tests work out.  But before I can test, I 
> need a decent bit counter.  (shift, xor, &, and | are already present 
> for integer values, but I also need to count the number of "true" items 
> after the logical operation.  So if a bitset is the correct approach, 
> 

Whether or not gmpy2 is considered light-weight is debateable. :)

> I'll need it to implement those operations, or their equivalents in 
> terms of union and intersection.)
> 
> 
> 
> Or do I need to drop into C for this?
> 

[1] http://code.google.com/p/gmpy/

> 
> 
> -- 
> 
> Charles Hixson

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web