10 Ways to Make Python Go Faster
On the “Sphere Online Judge” competition site, there are hundreds of programming challenges which you can attempt to solve in any of 40+ different programming languages. You simply submit your code, and the online judge will execute the code in a controlled environment. If you’re program generates the correct output (answers the set problem) within a specified time limit, you get some points on the scoreboard.
Here’s the catch: The time limit is the same no matter what language you are using. This obviously puts interpreted languages like Python at a disadvantage, and often you need to squeeze every last ounce of speed from you algorithm. Many problems have never been solved in Python due to the time limit… it pays to check whether there have been any sucessful Python solutions submitted for a given problem before getting too frustrated trying to find a fast enough solution.
So without further ado, here’s what SPOJ has taught me about speeding up Python code:
- Optimise the innermost loop. Most of the time when a program is taking a long time to run it is iterating over a loop, or nested loops. The rest of the program hardly matters as long as this innermost loop looks good. Reduce the number of operations being performed where possible. If the same value is being calculated more than once inside that loop, calculate it once and reuse the stored result! If the same value being calculated each time through the loop, why not calculate it just once before the loop? Basically you want your innermost loop to do as little work as possible.
- Function calls are expensive. If you’ve written a function that you’re calling from within a loop, consider getting rid of it and put that code inside your loop instead. This can make a huge difference to the speed of your program.
- Use built in types such as int, float, str and not your own object classes where possible.
- Perform Integer operations and not float operations where possible.
- Don’t code something yourself if there is already a built-in Python function or library that does the same thing. The built-in option is probably written in C and will win every time. To this end, familiarize yourself with useful standard library modules such as itertools. They are there to make your life easier and your code faster. Also review the builtins filter, map, any, all and sum. filter and map work well with lambda functions, so be sure you know how to write those aswell.
- While not available in SPOJ, learn what Numpy is and how to use it. With it you can quickly apply operations to entire array of values at the speed of C, rather than iterate over a list of values at the speed of Python.
- Sometimes a SPOJ problem requires a vast amount of data to be read from stdin. Use sys.stdin.readline() rather than input() or raw_input(). It’s much faster, and every millisecond counts. If you’re wondering whether sys.stdout.write() may offer similar benifits, in my experience print is just as fast so you might as well stick with that.
- Leap before you look. Otherwise known as EAFP (‘easier to ask forgiveness than permission’). This basically means that you should catch and deal with exceptions rather than try to avoid them (with if/else statements for example). Speed-wise this works well if you expect the error condition to occur infrequently. In my experience there seems to be a tipping point where if the exception is being caught too often the code will actually run faster if you avoid the error. Experiment with both approaches to see which runs fastest in your case. Check out this link for an example of the technique.
- Turn off automatic garbage collection. Very easy to do, and effective. Simply import gc; gc.disable().
- Experiment with using Psyco to speed up your program. Results will vary depending on your program, and it can even slow down some programs. However, it is so easy to use that it is worth a try. The most simple usage is:
import psyco psyco.full()
Remember though that many of these techniques may diminish the clarity and elegance in your Python code (with a few notable exceptions which will enhance your code). However, when you simply must have more speed, the above techniques may be useful!