Python is a great programming language: simple, expressive, compact.
In Codeforces, Python is often the best choice for Div 2 A and B problems. For example, problem 600A - Extract Numbers is very easy to write in Python: first tokenize the string with the built-in split()
function, then try to parse the integers with the built-in int()
, then output the comma-separated strings of results with ",".join(lst)
.
For the more complex problems, writing fast-enough Python code is often a challenge. Here is a list of tips to improve performance.
Use PyPy instead of the standard Python interpreter. According to 20 offical benchmarks it is on average 7 times faster than Python 2. PyPy2 is in my opinion the best option at the moment for competitive programming.
Append to an existing string with "+=" instead of concatenating more than two strings with "+" and storing the result with "=". (With two strings, both ways work fine.
s1 = s1 + s2
is fast because Python interpreter optimizes that tos1 += s2
.)string.join(iterable)
is as fast as it gets.list comprehension is faster than
for
loops.prefer
xrange()
instead ofrange()
, as the former returns an iterator, while the latter a new list.avoid
zip()
in Python 2: it constructs a new list. Instead use afor
loop . In Python 3, zip()` is fine, because there it returns an iterator.it's ok to use Python list as an array; it has O(1) element access time. It is NOT ok to use it as queue, even if the list is sorted. Use
collections.deque
instead if you need fast extraction of the max element.finally, realize that acceptable solutions to many Codeforces problems simply cannot be coded in Python, no matter how hard you try.
Experimental results
For the following tests I used a Lenovo laptop with Intel(R) Core(TM) i5-3427U CPU @ 1.80GHz, running Ubuntu 14.04.3 LTS. Software versions were: g++ 4.8.4, Python 2.7.6 and 3.4.3, PyPy 2.2.1 (Python 2.7.3) and 2.4.0 (Python 3.2.5). Each test was run 10 times, and the average results are reported.
I/O: Python vs. printf/scanf
vs. cin/cout
The problem: read a file with integers from 0 to 500000, store them in an array, then print out the array.
Implementations: scanf/printf, cin/cout, "fast" cin/cout, Python 2, Python 3.
The results:
scanf/printf: 0.1056 sec
cin/cout: 0.2274 sec
"fast" cin/cout: 0.0943 sec
Python 2: 0.3535 sec
PyPy 2: 0.1645 sec
Python 3: 0.2535 sec
PyPy 3: 0.3324 sec
Verdict: C++ is faster, but PyPy2 should be fast enough for most problems.
Iterator construction vs. list construction
The problem: sum all integers from 0 to 1e6 by using a for
loop.
The results:
Loop with range
:
python2: 0.502402067184 sec
pypy2: 0.0170 sec
Loop with xrange
:
python2: 0.334251880646 sec
pypy2: 0.0166962146759 sec
Loop with range
in Python3 that is in fact the same as xrange
in Python2:
python3: 0.6606624750002084 sec
pypy3: 0.0168 sec
Verdict: the differences between PyPy and standard Python are actually much much more important than range vs. xrange!
List construction: iterative growth vs. pre-reserving all memory at start.
The problem: Create a list with 1e6 elements.
The code when using iterative growth:
l = []
for x in range(1000000):
l.append(x)
The code when pre-reserving memory:
l = [0] * 1000000
for x in range(1000000):
l[x] = x
The results: With append:
python2: 0.698101997375 sec
pypy2: 0.483808994293 sec
python3: 0.844806871000 sec
pypy3: 0.510159969329 sec
With []:
python2: 0.618577957153 sec
pypy2: 0.0570020675659 sec
python3: 0.6261008259998 sec
pypy3: 0.0605409145355 sec
Verdict: PyPy is able to take advantage of the faster algorithm (with one-time growth), while standard Python is not able to. The PyPy speedup is an order-of-magnitude (~10 times).
Result summary: PyPy2 beats the others hands down in these tests. PyPy3 looks a bit unready at the moment, sometimes slower than the standard Python.