Generators/iterators, Pythonicity, and primes
John Posner
jjposner at snet.net
Sun Apr 12 14:03:27 EDT 2009
Duncan Booth wrote:
> John Posner <jjposner at snet.net> 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
More information about the Python-list
mailing list