|Thus Spake Jacek Generowicz On the now historical date of Thu, 08 Jan
2004 11:43:01 +0100|
I think this is generally interesting, and would be curious to see it,
if you'd care to share.
Sure thing. The functions at the top are naive prime enumeration
algorithms. I chose them because they're each of a general "looping"
nature and I understand the complexity and methods of each of them. Some
use lists (and hence linearly indexed) methods and some use dictionary(
and hence are has bound). One of them, sieve_list is commented out because
it has such dog performance that I decided I wasn't interested in
how well it optimized.
These tests are by no means complete, nor is this probably a good example
of profiling or the manner in which psyco is useful. It's just from an
area where I understood the algorithmic bottlenecks to begin with.
Sam Walters.
--
Never forget the halloween documents.
http://www.opensource.org/halloween/
""" Where will Microsoft try to drag you today?
Do you really want to go there?"""
from math import sqrt
def primes_list(Limits = 1,KnownPrimes = [ 2 ]):
RetList = KnownPrimes
for y in xrange(2,Limits + 1):
w = y
p, r = 0,0
for x in RetList:
if x*x > w:
RetList.append(w)
break
p,r = divmod(y,x)
if r == 0:
w = p
return RetList
def primes_dict(Limits = 1,KnownPrimes = [ 2 ]):
RetList = KnownPrimes
RetDict = {}
for x in KnownPrimes:
RetDict[x] = 1
w = x + x
n = 2
while w <= Limits + 1:
RetDict[w] = n
w += x
n += 1
p, r = 0,0
for y in xrange(2, Limits + 1):
for x, z in RetDict.iteritems():
if x*x > y:
RetDict[y] = 1
break
p,r = divmod(y,x)
if r == 0:
RetDict[y] = p
break
return RetList
def sieve_list(Limits = 1, KnownPrimes = [ 2 ]):
RetList = KnownPrimes
CompList = [ ]
for y in xrange(2, Limits + 1):
if y not in CompList:
w = y
n = 1
while w <= Limits:
CompList.append(w)
w += y
n += 1
return RetList
def sieve_list_2(Limits = 1, KnownPrimes = [ 2 ]):
SieveList = [ 1 ]*(Limits )
RetList = [ ]
for y in xrange(2, Limits + 1):
if SieveList[y-2] == 1:
RetList.append(y)
w = y + y
n = 2
while w <= Limits + 1:
SieveList[w - 2] = n
w += y
n += 1
return RetList
def sieve_dict(Limits = 1, KnownPrimes = [ 2 ]):
SieveDict = { }
RetList = KnownPrimes
for x in KnownPrimes:
SieveDict[x] = 1
w = x + x
n = 2
while w <= Limits + 1:
SieveDict[w] = n
n += 1
w += x
for y in xrange(2, Limits + 1):
if not SieveDict.has_key(y):
RetList.append(y)
w = y
n = 1
while w <= Limits + 1:
SieveDict[w] = n
w += y
n += 1
return RetList
if __name__ == "__main__":
import sys
import profile
import pstats
import psyco
#this function wraps up all the calls that we wish to benchmark.
def multipass(number, args):
for x in xrange(1, number + 1):
primes_list(args, [ 2 ])
print ".",
sys.stdout.flush()
primes_dict(args, [ 2 ])
print ".",
sys.stdout.flush()
#Do not uncomment this line unless you have a *very* long time to wait.
#sieve_list(args)
sieve_dict(args, [ 2 ])
print ".",
sys.stdout.flush()
sieve_list_2(args, [ 2 ])
print "\r \r%i/%i"%(x, number),
sys.stdout.flush()
print "\n"
#number of times through the test
passes = 5
#find all primes up to maximum
maximum = 1000000
#create a profiling instance
#adjust the argument based on your system.
pr = profile.Profile( bias = 7.5e-06)
#run the tests
pr.run("multipass(%i, %i)"%(passes,maximum))
#save them to a file.
pr.dump_stats("primesprof")
#remove the profiling instance so that we can get a clean comparison.
del pr
#create a profiling instance
#adjust the argument based on your system.
pr = profile.Profile( bias = 7.5e-06)
#"recompile" each of the functions under consideration.
psyco.bind(primes_list)
psyco.bind(primes_dict)
psyco.bind(sieve_list)
psyco.bind(sieve_list_2)
psyco.bind(sieve_dict)
#run the tests
pr.run("multipass(%i, %i)"%(passes,maximum))
#save them to a file
pr.dump_stats("psycoprimesprof")
#clean up our mess
del pr
#load and display each of the run-statistics.
pstats.Stats('primesprof').strip_dirs().sort_stats('cum').print_stats()
pstats.Stats('psycoprimesprof').strip_dirs().sort_stats('cum').print_stats()
XML is slow by design, but in