Ruby and Python (was Re: Why is Python a good first scripting language?)

[Patrick Ellis]

"Michael Hudson" <mwh at python.net> wrote:
>
> This sieve is the second quickest I know in Python (it's due to Tim
> Peters):
>
> def sieve(n):
>     if n < 2:
>         return []
>     limit = int(math.sqrt(n))
>     primes = range(1, n+1, 2)
>     primes[0] = 0
>     n = len(primes)
>     for p in primes:
>         if not p: continue
>         if p <= limit:
>             # note that p*p is odd, so no need to subtract 1
>             # before shifting right -- same thing in the end
>             for i in xrange((p*p)>>1, n, p):
>                 primes[i] = 0
>             continue
>         break
>     primes[0] = 2
>     return filter(None, primes)
>
> This is from this thread
>
http://groups.google.com/groups?threadm=36921CBF.4A5450FB%40appliedbiometric
s.com
> back in 1999, which is fun reading.
>
> Interesting!  Tim's version is quicker with python 2.3.  I'd dig into
> why, if I cared <wink>.

I was playing with this and found that looping on this function resulted in
increasing run time for each iteration (for Python 2.2.1 on Windows ME).

for i in range(10):
    start = time.time()
    primes = sieve(10000000)
    stop = time.time()
    primes = None
    print "Primes took %7.3f seconds"%((stop-start))

Results in:

Primes took   6.370 seconds
Primes took   7.470 seconds
Primes took   8.080 seconds
Primes took   8.300 seconds
Primes took   8.400 seconds
Primes took   8.460 seconds
Primes took   8.510 seconds
Primes took   8.570 seconds
Primes took   8.570 seconds
Primes took   8.620 seconds

Note that removing the primes = None line results in settling around 8.9
instead of 8.6. My guess is this has to do with allocating and deallocating
millions of integer objects to put in the primes list. The 0.3 sec
difference is how long it takes to deallocate the returned list. Python 2.3
does memory more efficiently and is why it runs faster.

I came up with a new version that uses the Numeric package. It is
algorithmically identical, just with a few implementation changes.

def sieve(n):
    if n < 2:
        return []
    limit = (int(math.sqrt(n)) / 2) + 1
    primes = Numeric.arrayrange(1, n+1, 2)
    n = len(primes)
    for p in primes[1:limit]:
        if p:
            # note that p*p is odd, so no need to subtract 1
            # before shifting right -- same thing in the end
            primes[(p*p)>>1::p] = 0
    return list(Numeric.nonzero(primes))

The same test as above results in:

Primes took   1.870 seconds
Primes took   1.810 seconds
Primes took   1.760 seconds
Primes took   1.810 seconds
Primes took   1.870 seconds
Primes took   1.750 seconds
Primes took   1.820 seconds
Primes took   1.810 seconds
Primes took   1.810 seconds
Primes took   1.810 seconds

Because it uses arrays that store the integers directly, instead of many
tiny integer objects, it doesn't have the memory management overhead and
resulting increasing runtime. The biggest speed increase is replacing the
inner loop with an assignment statement to a slice (which doesn't work with
lists).

8.57 sec / 1.81 sec = 4.7 times faster.

I was impressed with how easy it was to switch from list to Numeric array.
Just switching from range to arrayrange changes the entire function over,
without any other code changes. It was a good speedup by itself and
eliminated the memory allocation problems.

Patrick Ellis