List Count

[Blind Anagram]

On 23/04/2013 00:06, Oscar Benjamin wrote:
> On 22 April 2013 22:25, Blind Anagram <blindanagram at nowhere.org> wrote:
>> On 22/04/2013 21:18, Oscar Benjamin wrote:
>>> On 22 April 2013 17:38, Blind Anagram <blindanagram at 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