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<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.
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.
--
http://mail.python.org/mailman/listinfo/python-list
