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.
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
