Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!rt.uk.eu.org!newsfeed.xs4all.nl!newsfeed1.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Date: Mon, 22 Apr 2013 16:50:16 +0100
From: Blind Anagram <blindanagram@nowhere.org>
User-Agent: Mozilla/5.0 (Windows NT 6.2; WOW64; rv:17.0) Gecko/20130328 Thunderbird/17.0.5
MIME-Version: 1.0
Newsgroups: comp.lang.python
To: python-list@python.org
Subject: Re: List Count
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>
In-Reply-To: <mailman.927.1366644147.3114.python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Precedence: list
Message-ID: <mailman.928.1366645838.3114.python-list@python.org>
Lines: 64
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:44091

On 22/04/2013 16:14, Oscar Benjamin wrote:

> On 22 April 2013 15:15, Blind Anagram <blindanagram@nowhere.org> wrote:
>> On 22/04/2013 14:13, Steven D'Aprano wrote:
>>> On Mon, 22 Apr 2013 12:58:20 +0100, Blind Anagram wrote:
>>>
>>>> I would be grateful for any advice people can offer on the fastest way
>>>> to count items in a sub-sequence of a large list.
>>>>
>>>> I have a list of boolean values that can contain many hundreds of
>>>> millions of elements for which I want to count the number of True values
>>>> in a sub-sequence, one from the start up to some value (say hi).
>>>>
>>>> I am currently using:
>>>>
>>>>    sieve[:hi].count(True)
>>>>
>>>> but I believe this may be costly because it copies a possibly large part
>>>> of the sieve.
> [snip]
>>
>> But when using a sub-sequence, I do suffer a significant reduction in
>> speed for a count when compared with count on the full list.  When the
>> list is small enough not to cause memory allocation issues this is about
>> 30% on 100,000,000 items.  But when the list is 1,000,000,000 items, OS
>> memory allocation becomes an issue and the cost on my system rises to
>> over 600%.
> 
> Have you tried using numpy? I find that it reduces the memory required
> to store a list of bools by a factor of 4 on my 32 bit system. I would
> expect that to be a factor of 8 on a 64 bit system:
> 
>>>> import sys
>>>> a = [True] * 1000000
>>>> sys.getsizeof(a)
> 4000036
>>>> import numpy
>>>> a = numpy.ndarray(1000000, bool)
>>>> sys.getsizeof(a)  # This does not include the data buffer
> 40
>>>> a.nbytes
> 1000000
> 
> The numpy array also has the advantage that slicing does not actually
> copy the data (as has already been mentioned). On this system slicing
> a numpy array has a 40 byte overhead regardless of the size of the
> slice.
> 
>> I agree that this is not a big issue but it seems to me a high price to
>> pay for the lack of a sieve.count(value, limit), which I feel is a
>> useful function (given that memoryview operations are not available for
>> lists).
> 
> It would be very easy to subclass list and add this functionality in
> cython if you decide that you do need a builtin method.

Thanks Oscar, I'll take a look at this.

But I was really wondering if there was a simple solution that worked
without people having to add libraries to their basic Python installations.

As I have never tried building an extension with cython, I am inclined
to try this as a learning exercise if nothing else.