Re: bit count or bit set && Python3

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!goblin2!goblin.stu.neva.ru!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path	<charleshixsn@earthlink.net>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.002
X-Spam-Evidence	'H': 1.00; 'S': 0.00; 'compiler': 0.05; 'pypy': 0.07; 'python': 0.09; 'subject:Python3': 0.09; 'subject:set': 0.09; 'cc:addr:python-list': 0.10; 'def': 0.10; '2.7:': 0.16; 'bitwise': 0.16; 'guessing': 0.16; 'message-id:@earthlink.net': 0.16; 'oct': 0.16; 'received:dsl.mindspring.com': 0.16; 'subject:bit': 0.16; 'to:addr:pearwood.info': 0.16; 'to:addr:steve+comp.lang.python': 0.16; "to:name:steven d'aprano": 0.16; 'string': 0.17; 'wrote:': 0.17; '>>>': 0.18; 'bit': 0.21; 'import': 0.21; 'operations.': 0.22; 'cc:2**0': 0.23; 'cc:addr:python.org': 0.25; 'header:In-Reply-To:1': 0.25; 'header :User-Agent:1': 0.26; 'am,': 0.27; '(as': 0.27; 'chris': 0.28; 'clever': 0.29; "d'aprano": 0.29; 'fast.': 0.29; 'steven': 0.29; 'unlikely': 0.29; "i'm": 0.29; 'that.': 0.30; 'fri,': 0.30; 'point': 0.31; 'int': 0.33; 'know.': 0.33; 'version': 0.34; 'skip:b 20': 0.34; 'christian': 0.34; 'faster': 0.35; 'really': 0.36; 'but': 0.36; 'compare': 0.36; "i'll": 0.36; 'skip:4 10': 0.37; 'subject:: ': 0.38; 'some': 0.38; 'times': 0.63; 'skip:n 10': 0.63; 'number:': 0.65; 'results': 0.65; '26,': 0.65; '600': 0.71; 'guessed': 0.84; 'hand,': 0.97
Date	Thu, 25 Oct 2012 09:08:39 -0700
From	Charles Hixson <charleshixsn@earthlink.net>
User-Agent	Mozilla/5.0 (X11; Linux x86_64; rv:10.0.7) Gecko/20120922 Icedove/10.0.7
MIME-Version	1.0
To	Steven D'Aprano <steve+comp.lang.python@pearwood.info>
Subject	Re: bit count or bit set && Python3
References	<5089511E.4090009@earthlink.net> <k6bllq$3gt$1@ger.gmane.org> <mailman.2849.1351179123.27098.python-list@python.org> <50896152$0$29978$c3e8da3$5496439d@news.astraweb.com>
In-Reply-To	<50896152$0$29978$c3e8da3$5496439d@news.astraweb.com>
Content-Type	text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding	7bit
Cc	"comp.lang.python" <python-list@python.org>
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.15
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list/>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.2867.1351199601.27098.python-list@python.org> (permalink)
Lines	48
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1351199601 news.xs4all.nl 6984 [2001:888:2000:d::a6]:49570
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:32166

Show key headers only | 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

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