[Tutor] Optimisation of prime number program (cont. from finding prime numbers)

[Boykie Mackay]

Ok,I have learnt how to generate prime numbers and how to 'split'
input.The above was to help me solve the second 'SPOJ'
challenge,PRIME1.The challenge can be found at
 

I have written my solution and tested it and it works fine,but
unfortunately it is times out when tested by 'SPOJ'.I don't know whether
it times out because it is inherently slow or because a certain
condition takes it into endless loops.I think it is simply because it
needs further optimisation.I have researched as much as I could but
can't find any way to improve the speed of the program (problem with
being a newbie is you don't know what you don't know!)

Could you please look at the program (attached) and advise possible
optimisations or point me to possible resources that would help solve
this challenge.

Thanks,

Boyks 
#!/usr/bin/env python

'''A program to generate prime numbers when given 2 numbers'''

def isPrime(number):
number=abs(int(number))
#1 is not considered a prime number
if number<2:
return False
#2 is the only even prime number
if number==2:
return True
#no even prime numbers after 2
if not number&1:
return False
#to find all prime numbers we need to go up to the
#square root of the highest odd number
for x in range(3,int(number**0.5)+1,2):
if number%x==0:
return False
return True

def printOutListOfPrimes(startNum,endNum):

#startNum and endNum commented out.Will be collected from user input

#startNum=int(raw_input())
#endNum=int(raw_input())
for num in range(startNum,endNum):
check=isPrime(num)
if check==1:
print num


def getNumOfTimes():
times=int(raw_input())
return times
print times

def getValues():
 
val=[]
n=getNumOfTimes()
for r in range(n):
input=raw_input()
newInput=input.split()
   # val.append(newInput)
val+=newInput

return val

if __name__ == "__main__":

x=getValues()
y=0#variable to control the indices
for i in range(len(x)-1):
y=0 #to keep track of indices
printOutListOfPrimes(int(x[y]),int(x[y+1]))
print
y+=2


 


   












___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Optimisation of prime number program (cont. from finding prime numbers)

[Kent Johnson]

Boykie Mackay wrote:
> Ok,I have learnt how to generate prime numbers and how to 'split'
> input.The above was to help me solve the second 'SPOJ'
> challenge,PRIME1.The challenge can be found at
>  
> 
> I have written my solution and tested it and it works fine,but
> unfortunately it is times out when tested by 'SPOJ'.I don't know whether
> it times out because it is inherently slow or because a certain
> condition takes it into endless loops.I think it is simply because it
> needs further optimisation.I have researched as much as I could but
> can't find any way to improve the speed of the program (problem with
> being a newbie is you don't know what you don't know!)

Computing prime numbers is an area where picking a good algorithm is 
important. This page might help:
http://en.wikipedia.org/wiki/Prime_number#Location_of_prime_numbers

Depending on what ranges your program is working with, a sieve algorithm 
might be faster than checking each number individually.

Python is not very fast at raw arithmetic. The top 20 submissions to 
this problem are in C and C++ and have times <= 0.03. The top Python 
program has a time of .41, so you are starting out at a disadvantage.

If SPOJ allows you to use psyco then do so, that will make a big difference.
http://psyco.sourceforge.net/

Kent
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Optimisation of prime number program (cont. from finding prime numbers)

[Eric Brunson]

Boykie Mackay wrote:
> Ok,I have learnt how to generate prime numbers and how to 'split'
> input.The above was to help me solve the second 'SPOJ'
> challenge,PRIME1.The challenge can be found at
>  
>
> I have written my solution and tested it and it works fine,but
> unfortunately it is times out when tested by 'SPOJ'.I don't know whether
> it times out because it is inherently slow or because a certain
> condition takes it into endless loops.I think it is simply because it
> needs further optimisation.I have researched as much as I could but
> can't find any way to improve the speed of the program (problem with
> being a newbie is you don't know what you don't know!)
>   

One optimization, and this is only good for printing a list of primes, 
is that you only need to test a number's divisibility by all *primes* 
less than the square root of the number.

By keeping a list of the primes already calculated, I saw a 3 times 
increase in speed counting all the prime numbers between 2 and one million:

# test all numbers below sqrt(n)
ebrunsonlx(~)$ time python primes.py
78498 primes below 100

real0m14.496s
user0m14.367s
sys 0m0.127s

# keeping a list of primes
ebrunsonlx(~)$ time python primes.py
78498 primes below 100

real0m5.570s
user0m5.551s
sys 0m0.017s


Here's the code I used:

primes = []

def isPrime1( n ):
s = n**.5
for d in xrange( 2, int(s)+1 ):
if not n%d:
return False

return True

def isPrime2( n ):
global primes
s = n**.5
for d in primes:
if d>s:
break
if not n%d:
return False

primes.append( n )
return True



That's just the most obvious optimization.  I'd like to compare to the 
performance of Sieve of Eratosthanes, but I don't feel like coding it.

> Could you please look at the program (attached) and advise possible
> optimisations or point me to possible resources that would help solve
> this challenge.
>
> Thanks,
>
> Boyks 
>   
> 
>
> ___
> Tutor maillist  -  Tutor@python.org
> http://mail.python.org/mailman/listinfo/tutor

___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

[Tutor] Fwd: Optimisation of prime number program (cont. from finding prime numbers)

[Kalle Svensson]

Oops, forgot to send to the list.


Hi!

On 9/21/07, Boykie Mackay <[EMAIL PROTECTED]> wrote:
> Ok,I have learnt how to generate prime numbers and how to 'split'
> input.The above was to help me solve the second 'SPOJ'
> challenge,PRIME1.The challenge can be found at
> 
...
> Could you please look at the program (attached) and advise possible
> optimisations or point me to possible resources that would help solve
> this challenge.

Interesting problem! I've been experimenting a bit with it, but I'm
not anywhere near the runtimes shown in the judge system...

It definitely needs some kind of clever algorithm. My first thought
was to use the sieve of Erastothenes
(http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) to generate the
primes up front, but the maximum value of n is far too large. After
that, I tried a combination: generate the primes up to sqrt(max N) and
then divide larger numbers by those primes. If written in C, this runs
fast enough (0.7 seconds on my laptop for a larger test case) but my
Python implementation of the same algorithm still takes too long
(about 7.5 seconds for the same test).

I'd be very interested in hearing about how to write a Python program
for this problem that can handle for example the input

1
0 10

in less than a second.

Regards,
  Kalle
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

[Tutor] Quick question

[Tino Dai]

Is there a more pythonic way of doing this:

  if queuePacket.has_key('procSeq') and \
  queuePacket.has_key('opacSeq') and \
  queuePacket.has_key('keySeq') and \
  len(queuePacket['procSeq']) == 0 and \
  len(queuePacket['opacSeq']) == 0 and \
 len(queuePacket['keySeq']) == 0:


?

-Thanks,
Tino
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Quick question

[Kent Johnson]

Tino Dai wrote:
> Is there a more pythonic way of doing this:
> 
>   if queuePacket.has_key('procSeq') and \
>   queuePacket.has_key('opacSeq') and \
>   queuePacket.has_key('keySeq') and \
>   len(queuePacket['procSeq']) == 0 and \
>   len(queuePacket['opacSeq']) == 0 and \
>  len(queuePacket['keySeq']) == 0:

'procSeq' in queuePacket is a little better.

You could put all the tests in a loop with all():

if all( (key in queuePacket and len(queuePacket[key]) == 0)
 for key in ('procSeq', 'opaqSeq', 'keySeq')):

You could replace the test with something like
len(queuePacket.get(key, 'xxx'))==0

which I think is equivalent though maybe a bit obscure...

Kent
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Quick question

[Michael Langford]

Use the .get method of the dict to return a nonzero value (say None or -1)
when it can't find an item. That will half your test cases. Example of .get
below:

 --Michael

>>> foo = {}
>>> foo['d']=0
>>> foo['a']=1
>>> if(foo.get('a',1)==0 and foo.get('q',1)==0): print foo
... else: print "adsflkj"
...
adsflkj
>>> foo['q'] = 0
>>> if(foo.get('a',1)==0 and foo.get('q',1)==0): print foo
... else: print "adsflkj"
...
adsflkj
>>> foo['a'] = 0
>>> if(foo.get('a',1)==0 and foo.get('q',1)==0): print foo
... else: print "adsflkj"
...
{'a': 0, 'q': 0, 'd': 0}
>>>




-- 
Michael Langford
Phone: 404-386-0495
Consulting: http://www.TierOneDesign.com/
Entertaining: http://www.ThisIsYourCruiseDirectorSpeaking.com

On 9/21/07, Tino Dai <[EMAIL PROTECTED]> wrote:
>
> Is there a more pythonic way of doing this:
>
>   if queuePacket.has_key('procSeq') and \
>   queuePacket.has_key('opacSeq') and \
>   queuePacket.has_key('keySeq') and \
>   len(queuePacket['procSeq']) == 0 and \
>   len(queuePacket['opacSeq']) == 0 and \
>  len(queuePacket['keySeq']) == 0:
>
>
> ?
>
> -Thanks,
> Tino
>
>
> ___
> 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] Quick question

[Eric Brunson]

There are quite a few ways to do what you want.  Here's are a few 
variations on a theme:

try:
if not any( ( len(queuePacket['procSeq']),
  len(queuePacket['opacSeq']),
  len(queuePacket['keySeq']) ) ):
# Do your stuff here
do_stuff()
except KeyError:
pass


Or, using a generator:

try:
if not any( len(queuePacket[key]) 
for key in ( 'procSeq', 'opacSeq', 'keySeq' ) ):
# Do your stuff here
do_stuff()
except KeyError:
pass


Or, using a list comprehension:

try:
if not [ 1 for key in ( 'procSeq', 'opacSeq', 'keySeq' ) if 
len(queuePacket[key]) != 0 ] ):
# Do your stuff here
do_stuff()
except KeyError:
pass


Tino Dai wrote:
> Is there a more pythonic way of doing this:
>
>   if queuePacket.has_key('procSeq') and \
>   queuePacket.has_key('opacSeq') and \
>   queuePacket.has_key('keySeq') and \
>   len(queuePacket['procSeq']) == 0 and \
>   len(queuePacket['opacSeq']) == 0 and \
>  len(queuePacket['keySeq']) == 0:
>
>
> ?
>
> -Thanks,
> Tino
>
> 
>
> ___
> 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] Quick question

[Jerry Hill]

On 9/21/07, Tino Dai <[EMAIL PROTECTED]> wrote:
> Is there a more pythonic way of doing this:
>
>   if queuePacket.has_key('procSeq') and \
>   queuePacket.has_key('opacSeq') and \
>   queuePacket.has_key('keySeq') and \
>   len(queuePacket['procSeq']) == 0 and \
>   len(queuePacket['opacSeq']) == 0 and \
>  len(queuePacket['keySeq']) == 0:

Assuming we're talking about Python 2.5 or greater I find the
following pretty readable:

all(queuePacket.has_key(k) for k in ('procSeq', 'opacSeq', 'keySeq')) and \
all(len(queuePacket[k])==0 for k in ('procSeq', 'opacSeq', 'keySeq'))

If you're not familiar with how those work, they use generator
expressions, which are very similar to list comprehensions.  See PEP
289 [1] for more information on generator expressions, and either the
tutorial [2] or PEP 202 [3] for more on list comprehensions.

1: http://www.python.org/dev/peps/pep-0289/
2: http://docs.python.org/tut/node7.html#SECTION00714
3: http://www.python.org/dev/peps/pep-0202/

-- 
Jerry
___
Tutor maillist  -  Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor