[Tutor] Help Optimise Code

[Rich Lovely]

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