On Thu, 25 Oct 2012 09:17:40 -0700, rusi wrote:
> On Oct 25, 8:57 pm, Steven D'Aprano <steve
> +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
>> > <christ...@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.
>
> 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
--
http://mail.python.org/mailman/listinfo/python-list
