Re: [Tutor] Help Optimise Code
* Richard Lovely [EMAIL PROTECTED] [081123 11:35]: I've tried a the sieve of erath-whatever as in test_generator, implemented using itertools functions, but it hit max recusion depth somewhere before 1000 primes, and I'm after millions of primes. I found an old implementation for some exercise of the sieve of Eratosthenes in my backups and its not recursive but iterative: #!/usr/bin/env python l=1*[1] for i in range(2,len(l)): if l[i] == 1: print i for j in range(i+1,len(l)): if j%i == 0: l[j]=0 Yes, it is pretty slow for a range of a million, but it speeds up a little after half an hour or so :-) You might want to have a look at the bsd-games package, which includes a program named primes. It prints out primes at a reasonable speed - up to 4294967295 (the default). The manpage says: BUGS primes won't get you a world record. If you can get it to work faster in python? I doubt that. primes uses IIRC atkin-sieve: http://cr.yp.to/papers/primesieves.pdf; -- You have an ambitious nature and may make a name for yourself. ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Help Optimise Code
On Thu, Dec 4, 2008 at 11:38 AM, Jörg Wölke [EMAIL PROTECTED] wrote: #!/usr/bin/env python l=1*[1] for i in range(2,len(l)): if l[i] == 1: print i for j in range(i+1,len(l)): if j%i == 0: for j in range(2*i, len(l), i): would be much faster, avoiding all the division. Kent ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Help Optimise Code
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 x10). 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 +, 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
Re: [Tutor] Help Optimise Code
On Wed, Nov 19, 2008 at 8:13 AM, Richard Lovely [EMAIL PROTECTED] wrote: Please don't suggest changing languages. I like python. Although if you want to write an extension for me, and provide the source and a makefile, please feel free. I have a MinGW install that's doing nothing. (Just kidding - almost.) Take a look at psyco, Cython, ShedSkin, Pyrex... Kent ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
[Tutor] Help Optimise Code
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 knownPrimes = array.array(L,(3,5)) # 'L' for unsigned long - not tested if using a smaller type is faster for x in count2(7): sqrtX = sqrt(x) # take extra function calls out of the inner loop 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 I've tried a the sieve of erath-whatever as in test_generator, implemented using itertools functions, but it hit max recusion depth somewhere before 1000 primes, and I'm after millions of primes. I'm not particularly bothered about startup overheads, just the loops. Quick thought: would the following work (I'm on a public computer without python, so can't test): Code: Select all def iprimes(): 'generate an endless sequence of prime numbers' yield 2 yield 3 yield 5 sqrt = math.sqrt knownPrimes = array.array(L,(3,5)) # 'L' for unsigned long - not tested if using a smaller type is faster for x in count2(7): sqrtX = sqrt(x) # take extra function calls out of the inner loop for test in ((not x % p) and -1 or p sqrtX for p in knownPrimes)): # a generator _should_ be faster... if test == -1: # (not x % p) == true break elif test: # (p sqrtX) == true yield x knownPrimes.append(x) break Please don't suggest changing languages. I like python. Although if you want to write an extension for me, and provide the source and a makefile, please feel free. I have a MinGW install that's doing nothing. (Just kidding - almost.) This is NOT homework. -- Richard Roadie Rich Lovely, part of the JNP|UK Famile www.theJNP.com ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Help Optimise Code
On Wed, Nov 19, 2008 at 8:13 AM, Richard Lovely [EMAIL PROTECTED] 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. You might be interested in this recipe and discussion: http://code.activestate.com/recipes/366178/ According to Wikipedia, the siev of Atkin is faster than sieve of Eratosthenes: http://en.wikipedia.org/wiki/Sieve_of_Atkin This is what I've got so far: 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 You are duplicating your tests, why not if (not x % p): break elif p sqrtX: ... ? Kent ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Help Optimise Code
On Wed, 19 Nov 2008 13:13:18 +, 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
