Velocity Reviews > Re: bit count or bit set && Python3

# Re: bit count or bit set && Python3

Steven D'Aprano
Guest
Posts: n/a

 10-25-2012
On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote:

> On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes <(E-Mail Removed)>
> 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=10000, 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

rusi
Guest
Posts: n/a

 10-25-2012
On Oct 25, 8:57*pm, Steven D'Aprano <steve
(E-Mail Removed)> wrote:
> On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote:
> > On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes <(E-Mail Removed)>
> > 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=10000, 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?

Chris Angelico
Guest
Posts: n/a

 10-25-2012
On Fri, Oct 26, 2012 at 3:17 AM, rusi <(E-Mail Removed)> wrote:
> On Oct 25, 8:57 pm, Steven D'Aprano <steve
> (E-Mail Removed)> wrote:
>> py> min(t.repeat(number=10000, 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

rusi
Guest
Posts: n/a

 10-25-2012
On Oct 25, 9:30*pm, Chris Angelico <(E-Mail Removed)> wrote:
> On Fri, Oct 26, 2012 at 3:17 AM, rusi <(E-Mail Removed)> wrote:
> > On Oct 25, 8:57 pm, Steven D'Aprano <steve
> > (E-Mail Removed)> wrote:
> >> py> min(t.repeat(number=10000, 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=

Mark Lawrence
Guest
Posts: n/a

 10-25-2012
On 25/10/2012 17:29, Chris Angelico wrote:
> On Fri, Oct 26, 2012 at 3:17 AM, rusi <(E-Mail Removed)> wrote:
>> On Oct 25, 8:57 pm, Steven D'Aprano <steve
>> (E-Mail Removed)> wrote:
>>> py> min(t.repeat(number=10000, 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.

Steven D'Aprano
Guest
Posts: n/a

 10-25-2012
On Thu, 25 Oct 2012 09:17:40 -0700, rusi wrote:

> On Oct 25, 8:57Â*pm, Steven D'Aprano <steve
> (E-Mail Removed)> wrote:
>> On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote:
>> > On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes
>> > <(E-Mail Removed)> 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=10000, 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: 10000 versus 100.

Using bin() and count() takes 0.6819710731506348/10000 = 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

Serhiy Storchaka
Guest
Posts: n/a

 10-25-2012
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=10000, repeat=7))

Neil Cerutti
Guest
Posts: n/a

 10-25-2012
On 2012-10-25, Steven D'Aprano <(E-Mail Removed)> wrote:
> On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote:
>> On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes
>> <(E-Mail Removed)>
>> 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

Neil Cerutti
Guest
Posts: n/a

 10-25-2012
On 2012-10-25, Neil Cerutti <(E-Mail Removed)> 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

Ian Kelly
Guest
Posts: n/a

 10-25-2012
On Thu, Oct 25, 2012 at 2:00 PM, Neil Cerutti <(E-Mail Removed)> 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.

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Charles Hixson Python 5 10-26-2012 04:30 PM Mark Lawrence Python 0 10-25-2012 04:24 PM MRAB Python 0 10-25-2012 03:18 PM Charles Hixson Python 0 10-25-2012 05:32 AM Charles Hixson Python 0 10-25-2012 02:19 AM

Advertisments