On Mar 18, 2005, at 02:15, Kent Johnson wrote:
Max Noel wrote:#!/usr/bin/env python
import math
import timeit
def primeConcise(limit):
return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] + range(3,x,2) if x%y==0]]
def primeConciseOptimized(limit):
return [2] + [x for x in xrange(3, limit, 2) if not [y for y in [2] + range(3,int(math.sqrt(x)), 2) if x%y==0]]
Hmm, I didn't know that 9 and 15 were prime...
When I'm doing timings like this I usually check the output. You can write a *very* fast algorithm if correctness does not count :-)
Damn. Got bitten again by the fact that range/xrange return start <= n < end and not start <= n <= end. Python lacks Ruby's range objects ( (start..end) or (start...end) depending on what you want).
In the (pythonized) words of E. Dijkstra, "if it doesn't have to work, pass is a good solution".
I blame sleep deprivation. -.-
Note I don't bother testing for divisibility by 2 since the candidates are all odd. This allows using xrange() instead of range() for a significant improvement.
My times: listPrimes 0.143752069048 primeConciseOptimized 0.586845814203 primeConciseOptimized2 0.391731351331
Kent
Mmh... Good one. Didn't think of it.
What can I say... I love stupid optimization challenges. Now I wonder if someone is going to dare come up and kick our asses with a version that does this with a C module... :D
-- Max
maxnoel_fr at yahoo dot fr -- ICQ #85274019
"Look at you hacker... A pathetic creature of meat and bone, panting and sweating as you run through my corridors... How can you challenge a perfect, immortal machine?"
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
