On 23/04/2013 00:06, Oscar Benjamin wrote: > On 22 April 2013 22:25, Blind Anagram <blindanag...@nowhere.org> wrote: >> On 22/04/2013 21:18, Oscar Benjamin wrote: >>> On 22 April 2013 17:38, Blind Anagram <blindanag...@nowhere.org> wrote: >> >> I also wondered whether I had missed any obvious way of avoiding the >> slicing cost (intellectually it seemed wrong to me to have to copy the >> list in order to count items within it). > [snip] >> >> I have looked at solutions based on listing primes and here I have found >> that they are very much slower than my existing solution when the sieve >> is not large (which is the majority use case). > > What matters is not so much the size of the sieve but the size of the > interval you want to query. You say that slicing cost is somehow > significant which suggests to me that it's not a small interval. An > approach using a sorted list of primes and bisect would have a cost > that is independent of the size of the interval (and depends only > logarithmically on the size of the sieve).
The issue here is that the prime number count is only one of the features of the class so I would have to essentially rewrite it to use the technique you suggest. And I found in my experiments that creating the sieve in the form of a list of primes (either directly or by converting a linear sieve) is a great deal slower than a simple sieve for the majority use cases where the sieve is not huge. I don't want to take up peoples time but I am willing to expose the code to anyone who has an interest as I am sure that it has wrinkles that others with more experience with Python would find. But I would also be interested to discover whether there is a rationale for not offering list.count(value, limit) as this seems to me a useful function which I have found myself wanting more than once now. Thank you again for your input, which I appreciate. Brian -- http://mail.python.org/mailman/listinfo/python-list
