Hi Sean!
Thanks for your measurements. In the meantime I did another amendment, leaving out the even numbers from the sieve. It goes like this:
def sieve(maximum):
nums = range(3, maximum+1, 2)
for p in nums:
if p:
if p*p > maximum: break
start = (p*p-2)//2
nums[start::p] = [False]*(1+((maximum-3)//2-start)//p)
return [2] + filter(None, nums)Perhaps not very elegant. But approximately twice as fast as the former version.
Best wishes, Gregor
Sean Perry schrieb:
Gregor Lingl wrote:
The following variation of your sieve, using extended slice assignment seems to be sgnificantly faster. Try it out, if you like.
Here are the numbers: Primes 1 - 1,000,000 timing: extendedSliceSieve: 0.708388 seconds listPrimes: 0.998758 seconds karlSieve: 1.703553 seconds primeConciseOptimized: 5.133922 seconds setSieve: 7.564576 seconds primeConcise: 1644.683214 seconds --> 27 minutes 24 seconds
if __name__ == '__main__': # setup timers as a list of tuples (name, timeit instance)
results = [] longest = 0 for t in timers: result = t[1].timeit(1) longest = max(longest, len(t[0])) results.append((t[0], result))
results.sort(lambda x, y: cmp(x[1], y[1]))
print "Primes 1 - 1,000,000 timing:"
format_str = "%%%ds: %%f seconds" % longest for i in results: print format_str % i _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
-- Gregor Lingl Reisnerstrasse 3/19 A-1030 Wien
Telefon: +43 1 713 33 98 Mobil: +43 664 140 35 27
Autor von "Python für Kids" Website: python4kids.net _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
