List Count

[Oscar Benjamin]

On 22 April 2013 15:15, Blind Anagram <blindanagram at 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.


Oscar