Re: [Tutor] primes

[Max Noel]

On Mar 17, 2005, at 23:54, Danny Yoo wrote:
Hi Gregor,
Here is one that's traduced... er... adapted from material from the
classic textbook "Structure and Interpretation of Computer Programs":
<SNIP>
    Ooh, nifty.
	Okay, I decided to learn how to use the timeit module, so I used it to 
compare my algorithm (which, I just noticed, is a Python implementation 
of the Sieve of Erastothenes) to the one Gregor originally posted 
(albeit slightly optimized -- the only even prime number is 2, so 
there's no need to test them), and a further optimized version of it 
(stops looping at sqrt(x)).
	While I was at it, I optimized my algorithm further (in both memory 
usage and speed): it uses xrange and doesn't bother testing even 
numbers.

	Now, I did expect my algorithm to be the fastest. What I didn't 
expect, though, was for the differences to be *that* massive. Letting 
all three functions loose on finding all the prime numbers from 2 to 
50000, I got the following results (test machine: G4 867 running Python 
2.3 on OS X 10.3.8):

listPrimes: 0.508284091949 seconds                      # my algorithm
primeConciseOptimized: 2.18135714531 seconds    # Gregor's, optimized
primeConcise: 399.251116991 seconds                     # Gregor's, (partially 
optimized)
	As I suspected, when increasing the range, so do the differences. 
listPrimes finds all prime numbers from 2 to 200000 in 2.55 seconds, 
primeConciseOptimized in 15.81. At that point I had dropped 
primeConcise, as it being O(n^3) as far as I can tell, it would have 
taken ages to run. However, I thought the difference between listPrimes 
and primeConciseOptimized would increase faster than that. So 
primeConciseOptimized seems like the best compromise between speed and 
conciseness.

        Here's the (final?) version of the script I used:
#!/usr/bin/env python
import math
import timeit
def primeConcise(limit):
    return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] 
+ range(3,x,2) if x%y==0]]

def primeConciseOptimized(limit):
    return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] 
+ range(3,int(math.sqrt(x)), 2) if x%y==0]]

def isPrime(x, primeList):
    limit = int(math.sqrt(x))
    for i in primeList:
        if x % i == 0:
            return False
        if i >= limit:
            break
    return True
def listPrimes(upperLimit):
    listOfPrimes = [2]
    for i in xrange(3, upperLimit, 2):
        if isPrime(i, listOfPrimes):
            listOfPrimes.append(i)
    return listOfPrimes
if __name__ == '__main__':
    t1 = timeit.Timer('listPrimes(50000)', 'from __main__ import 
listPrimes')
    t2 = timeit.Timer('primeConciseOptimized(50000)', 'from __main__ 
import primeConciseOptimized')
    t3 = timeit.Timer('primeConcise(50000)', 'from __main__ import 
primeConcise')
    print t1.timeit(1)
    print t2.timeit(1)
    print t3.timeit(1)


-- Max
maxnoel_fr at yahoo dot fr -- ICQ #85274019
"Look at you hacker... A pathetic creature of meat and bone, panting 
and sweating as you run through my corridors... How can you challenge a 
perfect, immortal machine?"

_______________________________________________
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor