Question

Hey guys, I was working on ps1a and this is my solution to the prime assignment: http://codepad.org/yL3U3Wet
It works fine, I believe, but it quickly starts to get slow, as the order of complexity is O(n^2), if I analysed it correctly.
Do you guys see any way to improve my code? Any opinion is welcome ^^.
Thanks in advance.

Answer 1

Howdy bmp. I do have a couple of suggestions that will definitely improve the performance of your algorithm. First, it is only necessary to check up to the square of a number for divisors. For example, 130 would need to be checked through 11. math.sqrt() will help you there. Second, you only need to check previous primes as divisors. Since you are already keeping track of the previously found primes, iterate over them instead of a 2..n range for maximum effect. In our example, you would only need to check 130 against 2, 3, 5, 7, and 11. 5 checks instead of 74. And the benefit scales roughly O(n^2) :-)

Answer 2

First, walkerp1 mistyped a little. He should have said "up to the square ROOT of a number," but I think his intent is made clear by the rest of his explanation.

Second, in your PrimeNumber() function you create a list of odd numbers to test as divisors. You don't need to actually create the list. You could iterate over the same range you iterated over to create the list. Remember that range() can take a third, optional argument that specifies the increment. But if you do walkerp1's second suggestion (only test primes as divisors) then this list would go away, anyway.

Third, "else: pass" is unnecessary. If you want to do nothing in the else case, just don't include an else statement. (I know "Think Like a Computer Scientist" implies that an if NEEDS an else, but he was actually saying something else, but with really poor wording.) I don't think this would improve performance by much, but a test I did earlier showed that moving a variable initialization outside of a loop increased performance by 30%, so it might make a little difference.

I did a performance analysis of someone else's code for this problem yesterday. I'll try to find it and post a link.

Answer 3

http://openstudy.com/groups/mit+6.00+intro+computer+science+%28ocw%29#/groups/mit+6.00+intro+computer+science+%28ocw%29/updates/4e910ef30b8bfb9f23e3a9f1

Answer 4

Thanks guys. I will try to implement with walkerp1 suggestion for checking for divisors and do some style checking with variable initialization outside loops as suggested. Yeah, I was quite sure that a list with odds was unnecessary. Gonna rework on it also.
What do you guys think about adding portability to the code? I mean, using xrange() instead of range() because of the Python 3 differences and stuff like that. Thanks again :-)

Answer 5

Hi guys, I wrote an improved version of my solution: http://codepad.org/W29Z4sWW
It is a great improvement from my last version(take 7919 for instance: from 7 seconds of running time to around 0.05 seconds), thanks :-)
Any others tips or ideas? Regards.

Answer 6

Your code looks good and it works. The only suggestions I have are minor and nitpicky, but you asked. ;)

First, stylistically PrimeNumber(n) has a strange contract. It takes a number, and if it's prime, returns it, else it returns None. A more natural function would be isPrime(n) that returns True if n is prime, and False otherwise. Try making that change and reworking your code to use the new function.

Second, in ProductPrimes() you have this block of code:
if x != None:
prior.append(x)
else:
pass
else:pass is always unnecessary. However, if you did have code in the else that needed to be there, then I would point out the style issue of putting a negative condition in an if statement. It's easier to read if the condition expression is positive.
if x == None:
pass
else:
prior.append(x)
Otherwise, when I'm reading the code to myself I'm saying, "If x isn't None do this, and if x is not not None do something else."

And the last suggestion is just another optimization. Since you're collecting the list of found primes, you can pass that list into isPrime() (or PrimeNumber()) and only test prime divisors up to sqrt(n).

If you want to tackle these fixes, do them one at a time, and test thoroughly after each change.