bit count or bit set && Python3

[Mark Lawrence]

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<christian at 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.)
>

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.