I recently downloaded the bitarray module from here, for a faster prime sieve, but the results are dismal.
from bitarray import bitarray
from numpy import ones
from timeit import timeit
def sieve1(n = 1000000):
'''Sieve of Eratosthenes (bitarray)'''
l = (n - 1)/2; a = bitarray(l); a.setall(True)
for i in xrange(500):
if a[i]:
s = i+i+3; t = (s*s-3)/2; a[t:l:s] = False
return [2] + [x+x+3 for x in xrange(l) if a[x]]
def sieve2(n = 1000000):
'''Sieve of Eratosthenes (list)'''
l = (n - 1)/2; a = [True] * l
for i in xrange(500):
if a[i]:
s = i+i+3; t = (s*s-3)/2; u = l-t-1
a[t:l:s] = [False] * (u/s + 1)
return [2] + [x+x+3 for x in xrange(l)]
def sieve3(n = 1000000):
'''Sieve of Eratosthenes (numpy.ones)'''
l = (n - 1)/2; a = ones(l, dtype=bool)
for i in xrange(500):
if a[i]:
s = i+i+3; t = (s*s-3)/2; a[t:l:s] = False
return [2] + [x+x+3 for x in xrange(l)]
print timeit(sieve1, number=10)
print timeit(sieve2, number=10)
print timeit(sieve3, number=10)
Here are the result -
1.59695601594
0.666230770593
0.523708537583
The bitarray sieve is more than twice as slow as a list.
Does anyone have suggestions for better arrays? Anything should be faster than a python list, or so I thought.
numpy.ones is fastest, but I don't like numpy since it takes a long time to import it.
I'm basically looking for a fast data-holder, which is mutable, and can hold True and False.
