On 22/04/2013 21:18, Oscar Benjamin wrote:
> On 22 April 2013 17:38, Blind Anagram <blindanag...@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
--
http://mail.python.org/mailman/listinfo/python-list
