- Code: Select all
`def primesFunUntil(n):`

marks = [True] * (n + 1)

d = 2

for d in range(2, 1 + int(round(math.sqrt(n)))):

if marks[d]:

for mult in range(2*d, n + 1, d):

marks[mult] = False

return marks

Some days ago I heard of Python's array module http://docs.python.org/2/library/array.html, defining efficient arrays of numeric values. I thought this should improve my sieve implementation, so I modified it:

- Code: Select all
`def primesFunUntilArrays(n):`

marks = array.array('b', [1] * (n + 1))

d = 2

for d in range(2, 1 + int(round(math.sqrt(n)))):

if marks[d]:

for mult in range(2*d, n + 1, d):

marks[mult] = 0

return marks

I was assuming that in the first case, the access time is not constant (as I read lists behave, in Python), while I assumed that in the second, where the size of the elements is specified by the 'b' parameter in the array creation, it would be. So, I expected a significant improvement. Here is the complete script to test both and compare, used for primes until 30,000,000:

- Code: Select all
`import math`

import array

import timeit

def primesFunUntil(n):

marks = [True] * (n + 1)

d = 2

for d in range(2, 1 + int(round(math.sqrt(n)))):

if marks[d]:

for mult in range(2*d, n + 1, d):

marks[mult] = False

return marks

def primesFunUntilArrays(n):

marks = array.array('b', [1] * (n + 1))

d = 2

for d in range(2, 1 + int(round(math.sqrt(n)))):

if marks[d]:

for mult in range(2*d, n + 1, d):

marks[mult] = 0

return marks

if __name__ == "__main__":

print("Time for naive implementation: %s." % timeit.timeit("primesFunUntil(3*10**7)", number=1, setup="from __main__ import primesFunUntil"))

print("Time for the implementation with arrays: %s." % timeit.timeit("primesFunUntilArrays(3*10**7)", number=1, setup="from __main__ import primesFunUntilArrays"))

It produces the very dissapointing result:

- Code: Select all
`Time for naive implementation: 8.21312978368488.`

Time for the implementation with arrays: 11.19651029153776.

Can someone shed some light and tell me what is going on here?

Thanks in advance!