Pyhon perfomance tips
Difference between en2 and en3, changed 364 character(s)
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 [problem:600A] 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 `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 intepreter. According to [20 offical benchmarks](http://speed.pypy.org/) it is on average 7 times faster than Python 2. PyPy2 is in my opionion the best option at the moment for competitive programming.↵

- Append to an existing string with "+=" instead of concatening **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 to `s1 += s2`.)↵

- `string.join(iterable)` is as fast as it gets.↵

- list comprehension is faster than `for` loops.↵

- prefer `xrange()` instead of `range()`, as the former returns an iterator, while the latter a new list.↵

- avoid `zip()` in Python 2 (constructs) a list, prefer a `for` loop instead. `zip()` is fine in Python 3 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.↵



### Experimental results↵

For the following tests I used a Lenovo laptop with Intel(R) Core(TM) i5-3427U CPU @ 1.80GHz. 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](http://pastebin.com/LbFKyXJM)[cin/cout](http://pastebin.com/jHgkrnxU)["fast" cin/cout](http://pastebin.com/6BGYQNe0)[Python 2](http://pastebin.com/4VwDk9iQ)[Python 3](http://pastebin.com/tTprhue4).↵

**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 1
0e6 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↵
 pypy
2:   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:↵

~~~~~↵
 pypy2:   0.483808994293
 sec
 python2: 0.698101997375
 sec
 pypy3:   0.510159969329
 sec
 python3: 0.844806871000
 sec
~~~~~↵

With []:↵

~~~~~↵
 pypy2:   0.0570020675659
 sec
 python2: 0.618577957153
 sec
 pypy3:   0.0605409145355
2246 sec
 python3: 0.6261008259998
562 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 unread at the moment, sometimes slower than the standard Python. 

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English kfx 2015-11-30 12:01:15 1
en8 English kfx 2015-11-30 11:59:55 139 Tiny change: 'ons were: `g++` 4.8.4, Py' -> 'ons were: g++ 4.8.4, Py'
en7 English kfx 2015-11-30 11:55:15 1 Tiny change: 'bit unread at the mo' -> 'bit unready at the mo'
en6 English kfx 2015-11-30 11:54:50 7
en5 English kfx 2015-11-29 16:21:48 195
en4 English kfx 2015-11-29 15:47:09 155
en3 English kfx 2015-11-29 15:43:56 364 (published)
en2 English kfx 2015-11-29 15:33:56 3561
en1 English kfx 2015-11-29 14:57:52 433 Initial revision (saved to drafts)