Path: csiph.com!usenet.pasdenom.info!gegeweb.org!usenet-fr.net!nerim.net!novso.com!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
Sender: skip.montanaro@gmail.com
In-Reply-To: <51756769.20206@nowhere.org>
References: <sridnffI6YhxuOjMnZ2dnUVZ7tSdnZ2d@brightview.co.uk> <5175377f$0$29977$c3e8da3$5496439d@news.astraweb.com> <517545F7.5090209@nowhere.org> <mailman.927.1366644147.3114.python-list@python.org> <51755C38.4000204@nowhere.org> <mailman.929.1366646795.3114.python-list@python.org> <51756769.20206@nowhere.org>
Date: Mon, 22 Apr 2013 12:48:10 -0500
Subject: Re: List Count
From: Skip Montanaro <skip@pobox.com>
To: Blind Anagram <blindanagram@nowhere.org>
Content-Type: text/plain; charset=UTF-8
Cc: python-list@python.org
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.933.1366652894.3114.python-list@python.org>
Lines: 53
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:44101

> But I was really wondering if there was a simple solution that worked
> without people having to add libraries to their basic Python installations.

I think installing numpy is approximately

    pip install numpy

assuming you have write access to your site-packages directory.  If
not, install using --prefix and set PYTHONPATH accordingly.

I forgot that Python also has an array module.  With numpy available,
mature, and well-supported, I imagine it doesn't get much love these
days though.  Still, I gave it a whirl:

#######################################
import random
import array
from timeit import Timer

import numpy

stuff = [random.random() < 0.5 for i in range(10**7)]
sieve1 = numpy.array(stuff, dtype=bool)
sieve2 = array.array('B', stuff)

setup = """from __main__ import sieve1, sieve2
from itertools import islice
hi = 7*10**6
"""

t1 = Timer("(True == sieve1[:hi]).sum()", setup)
t2 = Timer("sieve2[:hi].count(True)", setup)
# t3 = Timer("sum(islice(sieve, hi))", setup)
# t4 = Timer("sum(x for x in islice(sieve, hi) if x)", setup)
# t5 = Timer("sum(x for x in islice(sieve, hi) if x is True)", setup)
# t6 = Timer("sum(1 for x in islice(sieve, hi) if x is True)", setup)
# t7 = Timer("len(list(filter(None, islice(sieve, hi))))", setup)

print(min(t1.repeat(number=10)))
print(min(t2.repeat(number=10)))
# for t in (t1, t2, t3, t4, t5, t6, t7):
#     print( min(t.repeat(number=10)) )
#######################################

Performance was not all that impressive:

0.340315103531
5.42102503777

Still, you might fiddle around with it a bit.  Perhaps unsigned ints
instead of unsigned bytes will provide more efficient counting...

Skip