Duncan Booth wrote:
John Posner <[email protected]> wrote:
Do know what in the itertools implementation causes adding a 'if p <=
sqrt(n)' clause to *decrease* performance, while adding a
'takewhile()' clause *increases* performance?
I haven't timed it, but I would guess that the takewhile was faster
only because the sqrt(n) had been factored out of the loop. Try the
original loop again precalculating the sqrt(n) and see how that compares.
Here's my "timeit" scorecard, with repeat=5 (only the minimum value
reported) and number=5000:
**** all prev. primes
3.97347791658
**** prev. primes that don't exceed SQRT
6.23250413579
**** [CACHED] prev. primes that don't exceed SQRT
3.45557325672
**** [TAKEWHILE] prev. primes that don't exceed SQRT
0.371197373201
**** [TAKEWHILE] squares, using *, of prev. primes that don't exceed N
0.358001074011
**** [TAKEWHILE] squares, using **, of prev. primes that don't exceed N
0.383540147515
**** [TAKEWHILE, CACHED] squares, using *, of prev. primes that don't
exceed N
0.410309506343
**** [TAKEWHILE, CACHED] squares, using **, of prev. primes that don't
exceed N
0.401269222462
So ... adding the SQRT optimization degrades the performance
significantly, but adding CACHING to the SQRT optimization swings the
performance pendulum back to the "benefit" side. TAKEWHILE is a big win,
but adding CACHING to TAKEWHILE degrades performance.
The code (110 lines) is at http://cl1p.net/python_prime_generators/
-John
--
http://mail.python.org/mailman/listinfo/python-list
