[Tutor] List Splicing
bob gailer
bgailer at gmail.com
Thu Jun 18 03:30:17 CEST 2009
Robert Berman wrote:
> Greetings,
>
> 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=list()
> TheSieve = range(0,itemsin+1)
> TheSieve[1]=0
> for i in range(2,itemsin+1):
> if (TheSieve[i] > 0):
> j = i + i
> while (j <= itemsin):
> TheSieve[j] = 0
> j+=i
> return TheSieve
>
Observations:
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] + [1]*(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 [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
> 2)
>
> 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.
>
> Robert
>
>
>
> _______________________________________________
> Tutor maillist - Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>
>
--
Bob Gailer
Chapel Hill NC
919-636-4239
More information about the Tutor
mailing list