On a small side note, the docs say array.array is supposed to be
efficient. Testing has shown in this function, a list is faster (at
least for x<100000). A set is faster still - at least over the same
range on my computer,, but you can't guarantee ordering, which makes
it inconsistent - and potentially broken.
The version I've got in my original post (using a single variable and
short-circuiting logic) is almost twice as fast as the version using
two separate tests. I don't know why, so suggestions would be
appreciated.
I'll add in a version of the count6 function. I must have forgotten
that maths lesson.
I've just thought of something that might be faster than using mod,
but I'll have to wait until I get home to test it.
(using a list of itertools.cycle's to produce a true/false from a
tuple with prime length, yielding a number iff not any(l[:sqrtX]). No
division involved...) If that make no sense to anyone, it makes less
sense to me, sounds ok, though...
---
Richard "Roadie Rich" Lovely
Part of the JNP|UK Famille
www.theJNP.com
(Sent from my iPod - please allow me a few typos: it's a very small
keyboard)
On 19 Nov 2008, at 09:26 PM, Lie Ryan <[EMAIL PROTECTED]> wrote:
On Wed, 19 Nov 2008 13:13:18 +0000, Richard Lovely wrote:
I'm pretty new to code optimisation, so I thought I'd ask you all for
advice.
I'm making an iterative prime number generator. This is what I've
got so
far:
Code: Select all
import math, array
def count2(start_at=0):
'Yield every third integer, beginning with start_at'
# this has been
tested as faster than using itertools.count
while True:
yield start_at
start_at += 2
def iprimes():
'generate an endless sequence of prime numbers'
yield 2
yield 3
yield 5
sqrt = math.sqrt
# 'L' for unsigned long - not tested if
# using a smaller type is faster
knownPrimes = array.array("L",(3,5))
for x in count2(7):
# take extra function calls out of the inner loop
sqrtX = sqrt(x)
for p in knownPrimes:
test = (not x % p) and -1 or p > sqrtX
if test == -1: # (not > x % p) == true
break
elif test: # (p > sqrtX) == true
yield x
knownPrimes.append(x)
break
Do you know that every prime number is in the form 6*x+1 or 6*x-1,
except
2 and 3. This means that instead of checking all odd numbers, you
could
loop over 6 numbers then yield n - 1 and n + 1.
def count6(start):
while True:
start += 6
yield start - 1
yield start + 1
And I've seen that you generated prime by dividing things up (actually
modulus). Division and modulus is the slowest arithmetic operator,
avoid
it if you can. If you knows the upper bound beforehand, it is faster
to
use multiplication and an array of fixed size, i.e. "Sieve of
Erasthotenes". If you intend to generate primes without known upper
bound
though, using sieve complexify things up.
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
