[Tutor] List Splicing
bgailer at gmail.com
Thu Jun 18 03:30:17 CEST 2009
Robert Berman wrote:
> 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
By convention we like to use names beginning with CAPS for class names
and names beginning with lower for variable names. Not a requirement,
but it makes it easier for us to read the code.
There is no need for TheSieve=list() as the next statement overrides that.
There is no need to store the actual numbers in the list, as the list
index can serve that purpose.
You could instead build a list of 2 0s followed by all 1s: The Sieve =
[0,0] + *(itemsin-2).
> 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 : l1
> Out: [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 : l1[n+n:len(l1):n]
> Out: [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.
> Tutor maillist - Tutor at python.org
Chapel Hill NC
More information about the Tutor