[Tutor] List Splicing

[bob gailer]

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