Re: bit count or bit set && Python3
cas...@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.
--
http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On 2012-10-25, Ian Kelly wrote: > On Thu, Oct 25, 2012 at 2:00 PM, Neil Cerutti > wrote: >> Yes indeed! Python string operations are fast enough and its >> arithmetic slow enough that I no longer assume I can beat a >> neat lexicographical solution. Try defeating the following >> with arithmetic: >> >> def is_palindrom(n): >>s = str(n) >>return s = s[::-1] > > Problems like these are fundamentally string problems, not math > problems. The question being asked isn't about some essential > property of the number, but about its digital representation. > Certainly they can be reasoned about mathematically, but the > fact remains that the math being done is about the properties > of strings. The "unexpected" part, to me, is that an optimal arithmetic based solution conceptually is more efficient. You need to compute just half the digits of the number and then perform a contant compare operation. -- Neil Cerutti -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On 25-10-12 16:47, Charles Hixson 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?
>
Some time ago I implemented this. Maybe you can use it as inspiration.
def CardSet(iter):
bits = 0L
for el in iter:
bits = bits | (1L << el)
return CardSetType(bits)
def CSt(*args):
return CardSet(args)
class CardSetType:
def __init__(self, bits):
self.bits = bits
def __str__(self):
return '{' + ','.join(map(str , self)) + '}'
def __repr__(self):
return 'CSt(' + ','.join(map(str , self)) + ')'
def __eq__(self, term):
return self.bits == term.bits
def __contains__(self, el):
return (1L << el) & self.bits == 1L << el
def __and__(self, term):
return CardSetType(self.bits & term.bits)
def __or__(self, term):
return CardSetType(self.bits | term.bits)
def __xor__(self, term):
return CardSetType(self.bits ^ term.bits)
def __sub__(self, term):
return CardSetType(self.bits & ~term.bits)
def __le__(self, term):
return self.bits & term.bits == self.bits
def __ge__(self, term):
return self.bits | term.bits == self.bits
def __len__(self):
bits = self.bits
full = 1L
shift = 1L
index = 0
mask = []
while full < bits:
for i in range(index):
mask[i] = (mask[i] << shift) + mask[i]
mask.append(full)
full = (full << shift) + full
index = index + 1
shift = 2 * shift
shift = 1
for i in range(index):
bits = ((bits >> shift) & mask[i]) + (bits & mask[i])
shift = 2 * shift
return int(bits)
def incl(self, el):
self.bits = self.bits | 1L << el
def excl(self, el):
self.bits = self.bits & ~(1L << el)
def __iter__(self):
return SetIterator(self.bits)
class SetIterator:
def __init__(self, bits):
self.bits = bits
self.offset = 0
def __iter__(self):
return self
def next(self):
if self.bits == 0:
raise StopIteration
else:
while True:
shift = 0
delta = 1
full = 1L
while (self.bits & full) == 0:
full = (full << delta) + full
shift = delta
delta = delta * 2
if shift == 0:
break
self.offset = self.offset + shift
self.bits = self.bits >> shift
result = self.offset
self.offset = self.offset + 1
self.bits = self.bits >> 1
return result
--
http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On Thu, 25 Oct 2012 14:20:00 -0600, Ian Kelly wrote: > On Thu, Oct 25, 2012 at 2:00 PM, Neil Cerutti wrote: >> Yes indeed! Python string operations are fast enough and its arithmetic >> slow enough that I no longer assume I can beat a neat lexicographical >> solution. Try defeating the following with arithmetic: >> >> def is_palindrom(n): >>s = str(n) >>return s = s[::-1] > > Problems like these are fundamentally string problems, not math > problems. The question being asked isn't about some essential property > of the number, but about its digital representation. Speaking as somebody who sometimes pretends to be a mathematician, I think you are wrong there. The property of being a palindrome may have been invented in reference to strings, but it is also a mathematical property of a number. Properties of the digits of numbers are properties of the relationship between the number and some sequence of divisors (the powers of some base), which makes them numeric properties. It's interesting to consider properties of numbers which hold for *every* base. For example, I understand that the digits of pi are uniformly distributed regardless of which base you use. Certainly mathematicians frequently ask questions about the digits of numbers, generally in base ten but also in other bases. Since the digits of a number are based on the numeric properties of the number, they certainly are essential to the number (modulo some base). For example, apart from two itself[1], every prime number ends in a 1 bit in base two. In decimal, every factorial greater than 4! ends with a zero. A number is divisible by 9 if the sum of the (decimal) digits reduces to 9. A number is divisible by 5 if the last digit is 0 or 5. These are not accidents, they depend on the numeric properties. > Certainly they can > be reasoned about mathematically, but the fact remains that the math > being done is about the properties of strings. Strings of digits, which are numerically equal to the remainders when you divide the number by successively larger powers of some base.: 123 = 1*10**2 + 2*10**1 + 3*10**0 Hence, mathematical. Of course, none of this challenges the fact that, at least in Python, reasoning about digits is often best done on the string representation rather than the number itself. [1] Which makes 2 the oddest prime of all. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On 25/10/2012 17:08, Charles Hixson wrote:
On 10/25/2012 08:57 AM, Steven D'Aprano wrote:
On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote:
On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes
wrote:
Simple, easy, faster than a Python loop but not very elegant:
bin(number).count("1")
Unlikely to be fast.
Oh I don't know about that. Here's some timing results using Python 2.7:
py> from timeit import Timer
py> t = Timer('bin(number).count("1")', setup='number=2**10001-1')
py> min(t.repeat(number=1, repeat=7))
0.6819710731506348
Compare to MRAB's suggestion:
def count_set_bits(number):
count = 0
while number:
count += 1
number&= number - 1
return count
py> t = Timer('count_set_bits(number)',
... setup='from __main__ import count_set_bits; number=2**10001-1')
py> min(t.repeat(number=100, repeat=7))
4.141788959503174
That makes the "inelegant" solution using bin() and count() about 600
times faster than the mathematically clever solution using bitwise
operations.
On the other hand, I'm guessing that PyPy would speed up MRAB's version
significantly.
Really nice and good to know. I had guessed the other way. (As you
point out this is compiler dependent, and I'll be using Python3,
but...conversion from an int to a bit string must be a *lot* faster than
I had thought.)
The simple rule for Python performance is never guess anything as you'll
invariably be wrong, time it and/or profile it, then change your code if
and only if you have to.
--
Cheers.
Mark Lawrence.
--
http://mail.python.org/mailman/listinfo/python-list
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On 10/25/2012 08:57 AM, Steven D'Aprano wrote:
On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote:
On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes
wrote:
Simple, easy, faster than a Python loop but not very elegant:
bin(number).count("1")
Unlikely to be fast.
Oh I don't know about that. Here's some timing results using Python 2.7:
py> from timeit import Timer
py> t = Timer('bin(number).count("1")', setup='number=2**10001-1')
py> min(t.repeat(number=1, repeat=7))
0.6819710731506348
Compare to MRAB's suggestion:
def count_set_bits(number):
count = 0
while number:
count += 1
number&= number - 1
return count
py> t = Timer('count_set_bits(number)',
... setup='from __main__ import count_set_bits; number=2**10001-1')
py> min(t.repeat(number=100, repeat=7))
4.141788959503174
That makes the "inelegant" solution using bin() and count() about 600
times faster than the mathematically clever solution using bitwise
operations.
On the other hand, I'm guessing that PyPy would speed up MRAB's version
significantly.
Really nice and good to know. I had guessed the other way. (As you
point out this is compiler dependent, and I'll be using Python3,
but...conversion from an int to a bit string must be a *lot* faster than
I had thought.)
--
Charles Hixson
--
http://mail.python.org/mailman/listinfo/python-list
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On Thu, Oct 25, 2012 at 2:00 PM, Neil Cerutti wrote: > Yes indeed! Python string operations are fast enough and its > arithmetic slow enough that I no longer assume I can beat a neat > lexicographical solution. Try defeating the following with > arithmetic: > > def is_palindrom(n): >s = str(n) >return s = s[::-1] Problems like these are fundamentally string problems, not math problems. The question being asked isn't about some essential property of the number, but about its digital representation. Certainly they can be reasoned about mathematically, but the fact remains that the math being done is about the properties of strings. -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On 10/25/2012 12:13 PM, rusi wrote: On Oct 25, 7:56 pm, Charles Hixson 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On 2012-10-25, Neil Cerutti wrote: > Try defeating the following with arithmetic: > > def is_palindrom(n): >s = str(n) >return s = s[::-1] Sorry for the typos. It should've been: def is_palindrome(n): s = str(n) return s == s[::-1] -- Neil Cerutti -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On 2012-10-25, Steven D'Aprano wrote:
> On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote:
>> On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes
>>
>> wrote:
>>> Simple, easy, faster than a Python loop but not very elegant:
>>>
>>>bin(number).count("1")
>>
>> Unlikely to be fast.
>
> Oh I don't know about that.
Yes indeed! Python string operations are fast enough and its
arithmetic slow enough that I no longer assume I can beat a neat
lexicographical solution. Try defeating the following with
arithmetic:
def is_palindrom(n):
s = str(n)
return s = s[::-1]
> Here's some timing results using Python 2.7:
Excellent work.
You can of course drop to C for arithmetic and likely triumph
over Python strings. That's never been applicable for me, though.
--
Neil Cerutti
--
http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
Chris Angelico's suggestion:
>>> bitcount = bytes(bin(i).count("1") for i in range(256))
>>> t = Timer('sum(number.to_bytes((number.bit_length() + 7) // 8,'
... '"little").translate(bitcount))',
... setup='from __main__ import bitcount; number=2**10001-1')
>>> min(t.repeat(number=1, repeat=7))
--
http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On Thu, Oct 25, 2012 at 11:25 AM, Christian Gollwitzer 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 1-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=100, repeat=7))
0.634620810749
>>> 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=10, 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=10, repeat=7))
0.1247119396459766
--
http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On Thu, 25 Oct 2012 09:17:40 -0700, rusi wrote:
> On Oct 25, 8:57 pm, Steven D'Aprano +comp.lang.pyt...@pearwood.info> wrote:
>> On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote:
>> > On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes
>> > wrote:
>> >> Simple, easy, faster than a Python loop but not very elegant:
>>
>> >> bin(number).count("1")
>>
>> > Unlikely to be fast.
>>
>> Oh I don't know about that. Here's some timing results using Python
>> 2.7:
>>
>> py> from timeit import Timer
>> py> t = Timer('bin(number).count("1")', setup='number=2**10001-1')
>> py> min(t.repeat(number=1, repeat=7))
>> 0.6819710731506348
>>
>> Compare to MRAB's suggestion:
>>
>> def count_set_bits(number):
>> count = 0
>> while number:
>> count += 1
>> number &= number - 1
>> return count
>>
>> py> t = Timer('count_set_bits(number)',
>> ... setup='from __main__ import count_set_bits;
>> ... number=2**10001-1')
>> py> min(t.repeat(number=100, repeat=7))
>> 4.141788959503174
>>
>> That makes the "inelegant" solution using bin() and count() about 600
>> times faster than the mathematically clever solution using bitwise
>> operations.
>
> You meant 600% I think?
No, I mean a factor of 600 times faster. Look at the number of iterations
used in each test: 1 versus 100.
Using bin() and count() takes 0.6819710731506348/1 = 6.8e-5 seconds
on my computer; using MRAB's neat trick takes 4.141788959503174/100 =
0.041 seconds. 0.041/6.8e-5 is slightly over 600.
--
Steven
--
http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On Oct 25, 9:30 pm, Chris Angelico wrote: > On Fri, Oct 26, 2012 at 3:17 AM, rusi wrote: > > On Oct 25, 8:57 pm, Steven D'Aprano > +comp.lang.pyt...@pearwood.info> wrote: > >> py> min(t.repeat(number=1, repeat=7)) > >> 0.6819710731506348 > >> py> min(t.repeat(number=100, repeat=7)) > >> 4.141788959503174 > > >> That makes the "inelegant" solution using bin() and count() about 600 > >> times faster than the mathematically clever solution using bitwise > >> operations. > > > You meant 600% I think? > > It took six times longer to do one hundredth the iterations. > > ChrisA Oh! Missed the number= -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On 25/10/2012 17:29, Chris Angelico wrote: On Fri, Oct 26, 2012 at 3:17 AM, rusi wrote: On Oct 25, 8:57 pm, Steven D'Aprano wrote: py> min(t.repeat(number=1, repeat=7)) 0.6819710731506348 py> min(t.repeat(number=100, repeat=7)) 4.141788959503174 That makes the "inelegant" solution using bin() and count() about 600 times faster than the mathematically clever solution using bitwise operations. You meant 600% I think? It took six times longer to do one hundredth the iterations. ChrisA Oh no, not another PEP 393 foul up :) -- Cheers. Mark Lawrence. -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On Thu, Oct 25, 2012 at 9:24 AM, Mark Lawrence wrote: > On 25/10/2012 15:47, Charles Hixson 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 needed bitarray and bitstring are available on pypi. > There's also my bits_mod.py: http://stromberg.dnsalias.org/svn/bits/trunk/ I separated it out of my bloom filter code recently, to facilitate a prime number sieve. Behind the scenes it's an array of int's. -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On Fri, Oct 26, 2012 at 3:17 AM, rusi wrote: > On Oct 25, 8:57 pm, Steven D'Aprano +comp.lang.pyt...@pearwood.info> wrote: >> py> min(t.repeat(number=1, repeat=7)) >> 0.6819710731506348 >> py> min(t.repeat(number=100, repeat=7)) >> 4.141788959503174 >> >> That makes the "inelegant" solution using bin() and count() about 600 >> times faster than the mathematically clever solution using bitwise >> operations. > > You meant 600% I think? It took six times longer to do one hundredth the iterations. ChrisA -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On 25/10/2012 15:47, Charles Hixson 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 needed bitarray and bitstring are available on pypi. -- Cheers. Mark Lawrence. -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On Oct 25, 8:57 pm, Steven D'Aprano wrote:
> On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote:
> > On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes
> > wrote:
> >> Simple, easy, faster than a Python loop but not very elegant:
>
> >> bin(number).count("1")
>
> > Unlikely to be fast.
>
> Oh I don't know about that. Here's some timing results using Python 2.7:
>
> py> from timeit import Timer
> py> t = Timer('bin(number).count("1")', setup='number=2**10001-1')
> py> min(t.repeat(number=1, repeat=7))
> 0.6819710731506348
>
> Compare to MRAB's suggestion:
>
> def count_set_bits(number):
> count = 0
> while number:
> count += 1
> number &= number - 1
> return count
>
> py> t = Timer('count_set_bits(number)',
> ... setup='from __main__ import count_set_bits; number=2**10001-1')
> py> min(t.repeat(number=100, repeat=7))
> 4.141788959503174
>
> That makes the "inelegant" solution using bin() and count() about 600
> times faster than the mathematically clever solution using bitwise
> operations.
You meant 600% I think?
--
http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On Oct 25, 7:56 pm, Charles Hixson 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 ? -- http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote:
> On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes
> wrote:
>> Simple, easy, faster than a Python loop but not very elegant:
>>
>>bin(number).count("1")
>
> Unlikely to be fast.
Oh I don't know about that. Here's some timing results using Python 2.7:
py> from timeit import Timer
py> t = Timer('bin(number).count("1")', setup='number=2**10001-1')
py> min(t.repeat(number=1, repeat=7))
0.6819710731506348
Compare to MRAB's suggestion:
def count_set_bits(number):
count = 0
while number:
count += 1
number &= number - 1
return count
py> t = Timer('count_set_bits(number)',
... setup='from __main__ import count_set_bits; number=2**10001-1')
py> min(t.repeat(number=100, repeat=7))
4.141788959503174
That makes the "inelegant" solution using bin() and count() about 600
times faster than the mathematically clever solution using bitwise
operations.
On the other hand, I'm guessing that PyPy would speed up MRAB's version
significantly.
--
Steven
--
http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes wrote:
> Simple, easy, faster than a Python loop but not very elegant:
>
>bin(number).count("1")
Unlikely to be fast.
What you may want is some sort of hybrid loop/lookup approach. Do you
know what your highest bit number is going to be? For instance, are
all your integers 32-bit? You could use something like this:
c = bitcount[n&255] + bitcount[n>>8&255] + bitcount[n>>16&255] + bitcount[n>>24]
where bitcount is a list of 256 values, giving the counts for each
value from 0 to 255.
Profile and test. :)
ChrisA
--
http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
Am 25.10.2012 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)?
Simple, easy, faster than a Python loop but not very elegant:
bin(number).count("1")
Christian
--
http://mail.python.org/mailman/listinfo/python-list
Re: bit count or bit set && Python3
On 2012-10-25 15:47, Charles Hixson 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? There's a nice algorithm for counting the ones. It takes one iteration per set bit: def count_set_bits(number): count = 0 while number: count += 1 number &= number - 1 return count -- http://mail.python.org/mailman/listinfo/python-list
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 -- http://mail.python.org/mailman/listinfo/python-list
