[Tutor] List Splicing

Robert Berman bermanrl at cfl.rr.com
Thu Jun 18 00:03:05 CEST 2009


I am working on a 'simple' algorithm to solve the problem called PRIME1
explained at http://www.spoj.pl/problems/PRIME1/. 

I do have an algorithm based on the Sieve of Eratosthenes and it does
work as I am failing the project not because of a computational error
but because of the dreaded TLE (time limit exceeded) designator. I have
determined there are at least 3 areas for improvement. The first is
within my code where I am creating a list of the first million primes. 
The code is as follows:

def BuildSieve(itemsin):
    TheSieve = range(0,itemsin+1)
    for i in range(2,itemsin+1):
        if (TheSieve[i] > 0):
            j = i + i
            while (j <= itemsin):
                TheSieve[j] = 0
    return TheSieve

It is called with PrimaryList = BuildSieve(1000000)

I have read that list splicing rather than looping to set a range of
items to zero is the best approach. Given an example  list  of

In [53]: l1
Out[53]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Since 3 is a prime, we can eliminate all multiples of 3. Within l1,
these are expressed as

In [52]: l1[n+n:len(l1):n]
Out[52]: [6, 9, 12]

when n = 3. ( do know 12 would have been eliminated by the prime number

It would be great if I could say l1[n+n:len(l1):n] = 0 but obviously
that will fail for obvious reasons. I am looking for the right hand side
of the statement to set a list within the list to all zeros. Also, if
anyone had a relatively simple explanation why in Python this is faster
than a loop, I would really like to understand it.

Thanks for the input.


More information about the Tutor mailing list