On 22/04/2013 16:14, Oscar Benjamin wrote: > On 22 April 2013 15:15, Blind Anagram <blindanag...@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. -- http://mail.python.org/mailman/listinfo/python-list
