On 23/04/2013 00:01, Steven D'Aprano wrote: > On Mon, 22 Apr 2013 15:15:19 +0100, Blind Anagram wrote: > >> 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%. > > Buy more memory :-) > > >> 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). > > There is no need to complicate the count method for such a specialised > use-case. A more general solution would be to provide list views. > > Another solution might be to use arrays rather than lists. Since your > sieve list is homogeneous, you could possibly use an array of 1 or 0 > bytes rather than a list of True or False bools. That would reduce the > memory overhead by a factor of four, and similarly reduce the overhead of > any copying:
I did a lot of work comparing the overall performance of the sieve when using either lists or arrays and I found that lists were a lot faster for the majority use case when the sieve is not large. Brian -- http://mail.python.org/mailman/listinfo/python-list