Confusing performance results for prime
Greg Brunet
gregbrunet at NOSPAMsempersoft.com
Sat Oct 18 18:59:47 EDT 2003
Thanks for the responses! After some more testing based on the
responses I got, here's some additional notes:
- xrange doesn't make an appreciable difference for this situation.
- Comparing 'equivalent' Primes1 & Primes3 versions shows that the sqrt
(outside the loop) is a worthwhile optimization (especially for larger
tests) (confirming Georgy's post).
- The reason I seed primes with 3 instead of 2 is that I know that I
won't ever have a match on it (since my loop skips even numbers). This
lets me skip an extra test each time thru the loop. If I use that in
Bengt's x*x version, it cuts the disadvantage of that loop (compared to
the sqrt one) about in half.
- The really big improvement gain in Primes2 by performing the typecase
(to either int or long) is most likely due to avoiding throwing an
exception. I don't always see it (don't understand why it's not
consistent), but sometimes I get a: "DeprecationWarning: integer
argument expected, got float" in the 'for' statement in Primes2.
- I should have typecast to [int] instead of [long]. If I had done so,
the results would have matched my expectations.
- Once I got both Primes1 & 2 using comparable algorithms (see Primes1i
& Primes2i below), Primes1 does become increasingly more efficient than
Primes2 with longer lists, as one would expect, since it will perform
relatively fewer loops.
For anyone interested, here is my updated testing program. It tests
these versions of Primes1: original, int typecast, int typecast w/
xrange, int typecast w/ reversed if tests, long typecast. If you run it,
you'll note that I skip testing the original Primes2, since the warning
exception makes it run MUCH longer (like 400% times longer than
Primes1i). It also has Bengt's Primes3 (and my change of it to skip
[2], then add it back in: Primes3a). Finally, it has another
interesting algorithm (Primes4) that I saw (in cookbook? - don't
remember anymore). I also don't run it in the comparative tests because
it is VERY slow (like 150x slower)! Be sure to run it long enough that
the measurement intervals are meaningful. I default the test to 10000
for older machines, but I'd recommend using a value large enough that
the fastest test takes at least 1 second
--
Greg
#------------------------------------------------------------
import math, time, sys
from math import sqrt
#import psyco
#psyco.full()
# Greg Brunet, Oct 18, 2003
# A check for a number being prime would generally see if
# it is odd and not divisible by any odd numbers up to it's
# square root. However, if we're generating a list of primes,
# we'll use that list to reduce the factors that we check
# against (Primes1 vs. Primes2).
#initial test using list of primes
def Primes1(y):
primes = [3]
for p in range(5, y, 2):
limit = sqrt(p)
for factor in primes:
if factor > limit: # then number is prime
primes.append(p)
break
elif p % factor == 0: # then it's *not* prime
break
#primes = [item for item in [2] + primes if x <= item < y]
return [2] + primes
#test using list of primes - w/ int typecast
# (so camparison is with 2 ints)
def Primes1i(y):
primes = [3]
for p in range(5, y, 2):
limit = int(sqrt(p))
for factor in primes:
if factor > limit: # then number is prime
primes.append(p)
break
elif p % factor == 0: # then it's *not* prime
break
#primes = [item for item in [2] + primes if x <= item < y]
return [2] + primes
#test using list of primes - w/ int typecast and xrange
# (to see if xrange is faster - no noticable difference)
def Primes1ix(y):
primes = [3]
for p in xrange(5, y, 2):
limit = int(sqrt(p))
for factor in primes:
if factor > limit: # then number is prime
primes.append(p)
break
elif p % factor == 0: # then it's *not* prime
break
#primes = [item for item in [2] + primes if x <= item < y]
return [2] + primes
#test using list of primes - w/ int typecast and reversing
# internal if tests (to see if we'll execute less if's that
# way (run faster) - no noticable difference)
def Primes1ir(y):
primes = [3]
for p in range(5, y, 2):
limit = int(sqrt(p))
for factor in primes:
if p % factor == 0: # then it's *not* prime
break
elif factor > limit: # then number is prime
primes.append(p)
break
#primes = [item for item in [2] + primes if x <= item < y]
return [2] + primes
#test using list of primes - w/ long typecast
# (initial optimization, before realizing that I should be
# using int instead!)
def Primes1l(y):
primes = [3]
for p in range(5, y, 2):
limit = long(sqrt(p))
for factor in primes:
if factor > limit: # then number is prime
primes.append(p)
break
elif p % factor == 0: # then it's *not* prime
break
#primes = [item for item in [2] + primes if x <= item < y]
return [2] + primes
#test using all odd numbers up to limit
# (but having a float in 'for..range(...' causes exception -> SLOW!)
def Primes2(y):
primes = [2,3]
for p in range(5, y, 2):
limit = sqrt(p) + 1
# check one extra (limit+3) to let us use (n>limit) below to
# know that we didn't break out of the loop
for n in range(3,limit+3,2):
if p % n == 0: # then it's *not* prime
break
if n > limit:
primes.append(p) # then number is prime
return primes
#test using all odd numbers up to limit - with int typecast
# (gets rid of exception)
def Primes2i(y):
primes = [2,3]
for p in range(5, y, 2):
limit = int(sqrt(p)) + 1
# check one extra (limit+3) to let us use (n>limit) below to
# know that we didn't break out of the loop
for n in range(3,limit+3,2):
if p % n == 0: # then it's *not* prime
break
if n > limit:
primes.append(p) # then number is prime
return primes
#test using all odd numbers up to limit - with int typecast
# (gets rid of exception, but not as fast as int!)
def Primes2l(y):
primes = [2,3]
for p in range(5, y, 2):
limit = long(sqrt(p)) + 1
# check one extra (limit+3) to let us use (n>limit) below to
# know that we didn't break out of the loop
for n in range(3,limit+3,2):
if p % n == 0: # then it's *not* prime
break
if n > limit:
primes.append(p) # then number is prime
return primes
#Bengt Richter's test avoiding sqrt call
def Primes3(prime_range_top):
primes = [2]
for prime_candidate in xrange(3,prime_range_top,2):
for p in primes:
if prime_candidate%p==0: break
if p*p>prime_candidate:
primes.append(prime_candidate)
break
else:
primes.append(prime_candidate)
return primes
#Bengt Richter's test
# - changed to skip checking for even (always false)
def Primes3a(prime_range_top):
primes = [3]
for prime_candidate in xrange(3,prime_range_top,2):
for p in primes:
if prime_candidate%p==0: break
if p*p>prime_candidate:
primes.append(prime_candidate)
break
else:
primes.append(prime_candidate)
return [2] + primes
#interesting approach, but VERY slow
def Primes4(y):
noprimes = [j for i in range(2, int(sqrt(y))+1) for j in range(i*2,
y, i)]
return [x for x in range(2, y) if x not in noprimes]
if __name__ == "__main__":
n=100000
if len(sys.argv)>1:
n=int(sys.argv[1])
times = []
primes = []
for pfun in (Primes1, Primes1i, Primes1ix, Primes1ir,
Primes1l, Primes2i, Primes2l, Primes3, Primes3a):
tb = time.time()
p = pfun(n)
primes.append(len(p))
dt = time.time() - tb
times.append(dt)
fastest = min(times)
print 'Prime number algorithms/optimizations - up to:', n
if (fastest==0):
print '*** Percentages are invalid (fastest time is 0) ***'
fastest = .01
for i, pfun in enumerate((Primes1, Primes1i, Primes1ix,
Primes1ir, Primes1l, Primes2i,
Primes2l, Primes3, Primes3a)):
print '%s: %s primes up to %s in %5.3f secs (+%3.1f%%)' % (
pfun.__name__, primes[i], n, times[i],
(times[i]-fastest)*100/fastest)
#------------------------------------------------------------
More information about the Python-list
mailing list