Python optimization for loops

Question

Here are two programs that naively calculate the number of primes & lt = n.
One is in Python and the other is in Java.

public class prime{ public static void main(String args[]){ int n = Integer.parseInt(args[0]); int nps = 0; boolean isp; for(int i = 1; i <= n; i++){ isp = true; for(int k = 2; k < i; k++){ if( (i*1.0 / k) == (i/k) ) isp = false; } if(isp){nps++;} } System.out.println(nps); } } `#!/usr/bin/python` import sys n = int(sys.argv[1]) nps = 0 for i in range(1,n+1): isp = True for k in range(2,i): if( (i*1.0 / k) == (i/k) ): isp = False if isp == True: nps = nps + 1 print nps 

Running them at n = 10000, I get the following timings.
shell: ~ $ time python prime.py 10000 && & time java prime 10000
1230

real 0m49.833s
User 0m49.815s
sys 0m0.012s
1230

real 0m1.491s
user 0m1.468s
sys 0m0.016s

Am I using it for loops in python incorrectly here or is python actually this much slower?

I'm not looking for an answer that is specifically designed for calculating prime numbers, but I'm wondering if python code is usually used in a more smart way.

Java code was compiled with javac 1.6.0_20
Run using java version "1.6.0_18"
OpenJDK Environment (IcedTea6 1.8.1) (6b18-1.8.1-0ubuntu1 ~ 9.10.1) OpenJDK Client VM (build 16.0-b13, mixed mode, sharing)

Python:
Python 2.6.4 (r264: 75706, December 7, 2009, 18:45:15)

Answer 1

As already stated, direct Python is not really made for this kind of thing. That the primary verification algorithm is naive is also not a point. However, with two simple things, I was able to significantly reduce Python time by using the original algorithm.

First put everything inside the function, name it main() or something else. This reduced the time on my machine in Python from 20.6 seconds to 14.54 seconds. Doing things around the world is slower than doing them in function.

Secondly, use the Psyco, JIT compiler. To do this, add two lines to the beginning of the file (and, of course, install psyco):

 import psyco psyco.full() 

This led to a final time of up to 2.77 seconds.

One last note. I decided to use Cython for this, and got the time down to 0.8533. However, knowing how to make a few changes to make it fast, Cython code is not what I recommend for the average user.

Answer 2

Yes, Python is slow, about a hundred times slower than C. You can use xrange instead of range for a little speedup, but other than that, it's fine.

Ultimately, what you are doing wrong is that you are doing it in plain Python, instead of using optimized libraries like Numpy or Psyco.

Java comes with a jit compiler that makes a big difference when you just crunch numbers.

Answer 3

You can make your Python about twice as fast by replacing this complex test with

 if i % k == 0: isp = False 

You can also do this about eight times faster (for n = 10000) than this by adding a gap after that isp = False.

Also do yourself a favor and skip even numbers (adding one to nps to start turning on 2).

Finally, you only need k to go to sqrt (i).

Of course, if you make the same changes to Java, it's still about 10 times faster than optimized Python.

Answer 4

Boy, when you said it was a naive realization, you probably weren’t joking!

But yes, a performance difference of one or two orders of magnitude is not a surprise when comparing a JIT-compiled optimized machine code with an interpreted language. An alternative Python implementation, such as Jython, which runs on a Java virtual machine, may be faster for this task; you could give him a whirlwind. Cython, which allows you to add static typing to Python and get C-like performance in some cases, may also be worth exploring.

Even when considering the standard Python interpreter, CPython, however, the question arises: is Python enough for this task? Will there be a time when you save a code entry in a dynamic language such as Python will offset the extra time it works? If you had to write this program in Java, would it be too much work to cost the problem?

Consider, for example, that a Python program running on a modern computer will be about as fast as a Java program running on a 10-year-old computer. The computer you had ten years ago was fast enough for many things, right?

Python has a number of functions that make it great for numerical work. These include an integer type that supports an unlimited number of digits, a decimal type with unlimited precision, and an additional library called NumPy, specifically for calculations. However, the speed of execution, as a rule, is not one of the main claims to fame. Where this is excellent, you need to get the computer to do what you want with minimal cognitive friction.

Answer 5

If you want to do it fast, Python is probably not the way forward, but you can speed it up a bit. First, you use a rather slow way to check for divisibility. Modulo is faster. You can also stop the inner loop (with k) as soon as it detects a match. I would do something like this:

 nps = 0 for i in range(1, n+1): if all(i % k for k in range(2, i)): # ie if divisible by none of them nps += 1 

This reduces it from 25 s to 1.5 s for me. Using xrange reduces to 0.9 s.

You can speed it up by saving the list of primes that you have already found, and only testing them, not every number until I (if I don't divide by 2, it won't divide by 4, 6, 8 ...).

Answer 6

Why aren't you posting something about memory usage, not just speed? Trying to get a simple servlet on tomcat spends 3GB on my server.

What you did with the examples there is not very good. You need to use numpy. Replace for / range with while loops, thereby avoiding the creation of a list.

Finally, python is well suited for crunching a number, at least by the people who do it right, and know what a sieve from Eratosthenes is or a mod operation.

Answer 7

There are many things you can do for this algorithm to speed it up, but most of them will also speed up the Java version. Some of them will speed up Python more than Java, so they deserve to be tested.

Here are just a few changes that speed it up from 11.4 to 2.8 seconds on my system:

 nps = 0 for i in range(1,n+1): isp = True for k in range(2,i): isp = isp and (i % k != 0) if isp: nps = nps + 1 print nps 

Answer 8

Python is a language that, paradoxically, is well suited for developing algorithms. Even a modified algorithm:

 # See Thomas K for use of all(), many posters for sqrt optimization nps = 0 for i in xrange(1, n+1): if all(i % k for k in xrange(2, 1 + int(i ** 0.5))): nps += 1 

Works well below one second. Code like this:

 def eras(n): last = n + 1 sieve = [0,0] + range(2, last) sqn = int(round(n ** 0.5)) it = (i for i in xrange(2, sqn + 1) if sieve[i]) for i in it: sieve[i*i:last:i] = [0] * (n//i - i + 1) return filter(None, sieve) 

faster. Or try these .

The thing is, python is usually fast enough to develop your solution. If it's not fast enough for production, use numpy or Jython to increase performance. Or move it to a compiled language, taking along with you your observations on the algorithms learned in python.

Answer 9

Yes, Python is one of the slowest practical languages ​​you will come across. While loops are a little faster than for i in xrange() , but in the end, Python will always be much, much slower than anything else.

Python has its place: the theory and ideas of prototyping, or in any situation where the ability to quickly generate code is more important than code performance.

Python is a scripting language. Not a programming language.