[Tutor] Help Optimise Code
Rich Lovely
roadierich at googlemail.com
Fri Nov 21 11:46:51 CET 2008
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 <lie.1296 at gmail.com> 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 at python.org
> http://mail.python.org/mailman/listinfo/tutor
More information about the Tutor
mailing list