Speed up this code?

[aomighty]

I'm creating a program to calculate all primes numbers in a range of 0
to n, where n is whatever the user wants it to be. I've worked out the
algorithm and it works perfectly and is pretty fast, but the one thing
seriously slowing down the program is the following code:

def rmlist(original , deletions):
return [i for i in original if i not in deletions]

original will be a list of odd numbers and deletions will be numbers
that are not prime, thus this code will return all items in original
that are not in deletions. For n > 100,000 or so, the program takes a
very long time to run, whereas it's fine for numbers up to 10,000.

Does anybody know a faster way to do this? (finding the difference all
items in list a that are not in list b)?

Thanks,
Martin

[bearophileHUGS]

I have tried this comparison, with a version I've modified a bit, I
have encoutered a problem in sieve_all, for example with n=10000, I
don't know why:

def sieve_all(n=100 ):
# yield all primes up to n
stream = iter(xrange(2, n))
while True:
p = stream.next()
yield p
def s1(p, stream):
# yield all non-multiple of p
return (q for q in stream if q%p != 0)
stream = s1(p, stream)
def primes(n):
"primes(n): return a list of prime numbers <=n."
# Recipe 366178 modified and fixed
if n == 2:
return [2]
elif n<2:
return []
s = range(3, n+2, 2)
mroot = n ** 0.5
half = len(s)
i = 0
m = 3
while m <= mroot:
if s[i]:
j = (m*m - 3) / 2
s[j] = 0
while j < half:
s[j] = 0
j += m
i += 1
m = 2 * i + 3
if s[-1] > n:
s[-1] = 0
return [2] + filter(None, s)

from time import clock
pmax = 21

for p in xrange(12, pmax):
n = 2 ** p
t1 = clock()
primes(n)
t2 = clock()
list(sieve_all( n))
t3 = clock()
print "primes(2^% s= %s):" % (p, n), round(t2-t1, 3), "s",
round(t3-t2, 3), "s"

import psyco
psyco.bind(prim es)
psyco.bind(siev e_all)

for p in xrange(12, pmax):
n = 2 ** p
t1 = clock()
primes(n)
t2 = clock()
list(sieve_all( n))
t3 = clock()
print "primes(2^% s= %s):" % (p, n), round(t2-t1, 3), "s",
round(t3-t2, 3), "s"
Bye,
bearophile

[John Machin]

On 27/05/2006 6:57 AM, be************@ lycos.com wrote:

I have tried this comparison, with a version I've modified a bit, I
have encoutered a problem in sieve_all, for example with n=10000, I
don't know why:

It might have been better use of bandwidth to give details of the
problem instead of all that extraneous source code.

Did you get this: """RuntimeError : maximum recursion depth exceeded"""?

You don't know why?

[Frank Millman]

Gregory Petrosyan wrote:

# Paul Rubin's version
gregory@home:~$ python -mtimeit "import test2" "test2.primes(1 000)"
100 loops, best of 3: 14.3 msec per loop

# version from the Cookbook
gregory@home:~$ python -mtimeit "import test1" "test1.primes(1 000)"
1000 loops, best of 3: 528 usec per loop

You are quite right, Gregory, my timings are way off.

I have figured out my mistake. Paul's function is a generator. Unlike a
normal function, when you call a generator function, it does not
actually run the entire function, it simply returns a generator object.
It only runs when you iterate over it until it is exhausted. I was
effectively measuring how long it took to *create* the generator, not
iterate over it.

Thanks for correcting me.

Frank

[Miki]

Hello Martin,

You can use gmpy (http://gmpy.sourceforge.net/)

def primes():
n = 2
while 1:
yield long(n)
n = gmpy.next_prime (n)

HTH,
Miki
http://pythonwise.blogspot.com/