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

Groups > comp.lang.python > #32166

Re: bit count or bit set && Python3

Show all headers | View raw

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<christian@python.org>
>> 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.
>
>
>
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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: bit count or bit set && Python3 Chris Angelico <rosuav@gmail.com> - 2012-10-26 02:31 +1100
  Re: bit count or bit set && Python3 Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-25 15:57 +0000
    Re: bit count or bit set && Python3 rusi <rustompmody@gmail.com> - 2012-10-25 09:17 -0700
      Re: bit count or bit set && Python3 Chris Angelico <rosuav@gmail.com> - 2012-10-26 03:29 +1100
        Re: bit count or bit set && Python3 rusi <rustompmody@gmail.com> - 2012-10-25 09:37 -0700
      Re: bit count or bit set && Python3 Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-10-25 17:44 +0100
      Re: bit count or bit set && Python3 Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-25 17:16 +0000
    Re: bit count or bit set && Python3 Serhiy Storchaka <storchaka@gmail.com> - 2012-10-25 22:07 +0300
    Re: bit count or bit set && Python3 Neil Cerutti <neilc@norwich.edu> - 2012-10-25 20:00 +0000
      Re: bit count or bit set && Python3 Neil Cerutti <neilc@norwich.edu> - 2012-10-25 20:04 +0000
      Re: bit count or bit set && Python3 Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-25 14:20 -0600
        Re: bit count or bit set && Python3 Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-25 23:48 +0000
        Re: bit count or bit set && Python3 Neil Cerutti <neilc@norwich.edu> - 2012-10-26 12:56 +0000
    Re: bit count or bit set && Python3 Charles Hixson <charleshixsn@earthlink.net> - 2012-10-25 09:08 -0700
    Re: bit count or bit set && Python3 Mark Lawrence <breamoreboy@yahoo.co.uk> - 2012-10-25 22:51 +0100

csiph-web