List Count

[Blind Anagram]

On 22/04/2013 21:18, Oscar Benjamin wrote:
> On 22 April 2013 17:38, Blind Anagram <blindanagram at nowhere.org> wrote:

[snip]

> If my description is correct then I would definitely consider using a
> different algorithmic approach. The density of primes from 1 to 1
> billlion is about 5%. Storing the prime numbers themselves in a sorted
> list would save memory and allow a potentially more efficient way of
> counting the number of primes within some interval.

That is correct but I need to say that the lengths I have been
describing are limiting cases - almost all of the time the sieve length
will be quite small.

But I was still interested to see if I could push the limit without
changing the essential simplicity of the sieve.

And here the cost of creating the slice (which I have measured) set me
wondering why a list.count(value, limit) function did not exist.

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]

> 
> So you're using about 1/5th of the memory with a list of primes
> compared to a list of True/False values. Further savings would be
> possible if you used an array to store the primes as 64 bit integers.
> In this case it would take about 400MB to store all the primes up to 1
> billion.

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

I have also tried counting using a loop such as:

  while i < limit:
    i = sieve.index(1, i) + 1
    cnt += 1

but this is slower than count even on huge lists.

Thank you again for your advice.

   Brian