List Count

[Oscar Benjamin]

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).


Oscar