Python Performance++
Difference between en3 and en4, changed 3,449 character(s)
I've listed my findings on experimenting with Python below, I hope they are useful to someone else who uses Python too.↵
↵
**TL;DR:** Links for the [master template](https://github.com/cheran-senthil/PyRival/blob/master/template/template.py) and [algorithms](https://github.com/cheran-senthil/PyRival).↵
↵
#### __Python Version__↵
↵
Based on a [prior blog postenchmarking](https://codeforces.me/blog/entry/21851) on Codeforces, it is quite conclusive that PyPy 2 is the fastest version of Python available on Codeforces.↵
↵
I have not had any incident where my code could not pPyPy 2 also has features not present in PyPy 3 such as random, and numpypy. Moreover, in Python 2, bytes and strings are equivalent, this is not the casse in PyPy 2 while passing in a different versionthon 3 and results in significant input and output slowdowns unless you use Bytes in Python 3.↵
↵
#### __Input & Output__↵
↵
Though there are faster ways to read input in general, the fastfor specific types (integers and non-strings). The safest way to safely redefine input and /print involves buffering the entire input and output. Please be careful of memory constraints in problems with small memory limits while usingwhile maintaining the same functionality is to use the following code.,↵
↵
```py↵
from __future__ import division, print_function↵
↵
import sys↵
from atexit import register↵
↵
if sys.version_info[0] < 3:↵
    from io import BytesIO as stream↵
else:↵
    from io import StringIO as stream↵
↵
↵
sys.stdin = stream(sys.stdin.read())↵
input = lambda: syimport os↵
import sys↵
from atexit import register↵
from io import BytesIO↵
↵
sys.stdin = BytesIO(os.read(0, os.fstdin.readline(at(0).rstrip('\r\n'_size))↵
↵
sys.stdout = streamBytesIO()↵
register(lambda: sys.__stdout__os.write(1, sys.stdout.getvalue()))↵
```↵
↵
#### __Fast Imports__↵
↵
Not all imports take an equal amount of time and memory at startup. The following list is a partially exhaustive list of what I have found to not take time and memory at startup in PyPy 2 on Codeforces. The commented code represents costly imports.↵
↵
```py↵
from __future__ import division, print_function↵
↵
import cmath↵
import itertools↵
import math↵
import operator as op↵
# import random↵
input = lambda: sys.stdin.readline().rstrip('\r\n')↵
```↵
↵
if your input does not involve strings, you can directly use,↵
↵
```py↵
import os↵
import sys↵
from atexit import register↵
from bisectio import bisect_left, bisect_right↵
# from collections import Counter, MutableSequence, defaultdict, deque↵
# from copy import deepcopy↵
# from decimal import Decimal↵
# from difflib import SequenceMatcher↵
# from fractions import Fraction↵
# from heapq import heappop, heappush↵
↵
if sys.version_info[0] < 3:↵
    # from cPickle import dumps↵
    from io import BytesIO as stream↵
    # from Queue import PriorityQueue, Queue↵
else:↵
    # from functools import reduce↵
    from io import StringIO as stream↵
    from math import gcd↵
    # from pickle import dumps↵
    # from queue import PriorityQueue, Queue↵
```↵
↵
#### __Python 3 Compatability__↵
↵
In Python 3BytesIO↵
↵
sys.stdout = BytesIO()↵
register(lambda: os.write(1, sys.stdout.getvalue()))↵
↵
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline↵
```↵
↵
This should be enough for the majority of cases, except in some rare cases where you have lot's of integers as input and would require custom str -> int.↵
↵
↵
You can also do much faster output in PyPy 2 by following ~pajenegod,2019-03-14's instructions [here](https://codeforces.me/blog/entry/65922?#comment-499139).↵
↵
↵
#### __Python 3 Compatability__↵
↵
print and division work differently between Python 2 and 3, but this can be remedied with imports from __future__↵
↵
Other differences are that dictionaries, range, filter, map, and zip all return iterators in Python 3 as opposed to lists in Python 2 and thus use less memory.↵
↵
This can be easily fixed with the code below.↵
↵
```py↵
if sys.version_info[0] < 3:↵
    class dict(dict):↵
        """dict() -> new empty dictionary"""↵
        def items(self):↵
            """D.items() -> a set-like object providing a view on D's items"""↵
            return dict.iteritems(self)↵
↵
        def keys(self):↵
            """D.keys() -> a set-like object providing a view on D's keys"""↵
            return dict.iterkeys(self)↵
↵
        def values(self):↵
            """D.values() -> an object providing a view on D's values"""↵
            return dict.itervalues(self)↵
↵
    def gcd(x, y):↵
        """gcd(x, y) -> int↵
        greatest common divisor of x and y↵
        """↵
        while y:↵
            x, y = y, x % y↵
        return xA minor issue in Python 2 is that the builtin gcd is much slower than writing your own iterative gcd, ideally having code for this is useful too.↵
↵
The code below should handle all of these issues, and let you write Python 3 code within Python 2.↵
↵
```py↵
""" Python 3 compatibility tools. """↵
from __future__ import division, print_function↵
↵
import itertools↵
import sys↵
↵
if sys.version_info[0] < 3:↵
    input = raw_input↵
    range = xrange↵
↵
    filter = itertools.ifilter↵
    map = itertools.imap↵
    zip = itertools.izip↵
↵
↵
def gcd(x, y):↵
    """ greatest common divisor of x and y """↵
    while y:↵
        x, y = y, x % y↵
    return x↵
```↵
↵
#### __Recursion Limit__↵
↵
In Python, we can use threading to increase the stack size to allow for large recursion limits, in PyPy this is not possible.↵
↵
However, [PyPy's docs](https://pypy.readthedocs.io/en/latest/stackless.html#recursion-depth-limit) give detail on how to resolve this issue. I've added some code below that should work for both.↵
↵
```py↵
def main():↵
    pass↵
↵
↵
if __name__ == '__main__':↵
    if 'PyPy' in sys.version:↵
        def bootstrap(c):↵
            callable However, overall, this is much slower than using your own stack in Python.↵
↵
```py↵
import sys↵
↵
if 'PyPy' in sys.version:↵
    from _continuation import continulet↵
else:↵
    import threading↵
↵
↵
def main():↵
    pass↵
↵
↵
if __name__ == '__main__':↵
    if 'PyPy' in sys.version:↵
↵
        def bootstrap(cont):↵
            call, arg = cont.switch()↵
            while True:↵
                   to = call, arg = cont.switch(to=continulet(lambda _, f, x: f(x), callable, arg)↵
               args: f(*args), callable, arg = c.switch(to=to))↵
↵
        cont = continulet(bootstrap)↵
        cont.switch()↵
↵
        main()↵
↵
    else:↵
        sys.setrecursionlimit(20971521 << 30)↵
        threading.stack_size(134217728 << 27)↵
↵
        main_thread = threading.Thread(target=main)↵
        main_thread.start()↵
        main_thread.join()↵
```↵
↵
#### __Credits__↵
↵
Special TThe vast majority of the techniques listed are thanks to ~pajenegod,2018-119-03-114 and ~Mukundan314,2018-11-11 for testing, debugging anhis repeated itechniquerations.↵
↵
_Please feel free to message/mail me with your findings too!_

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English c1729 2019-03-14 16:14:26 85
en4 English c1729 2019-03-14 16:10:25 3449 Tiny change: 'tly use,\n```py\ni' -> 'tly use,\n\n```py\ni'
en3 English c1729 2018-11-11 03:55:28 22 Tiny change: 'ival).\n\n#### _' -> 'ival).\n\n[cut]\n\n#### _' (published)
en2 English c1729 2018-11-11 03:44:12 126 Tiny change: '`\n\n#### Credits\n\nSpecia' -> '`\n\n#### __Credits__\n\nSpecia'
en1 English c1729 2018-11-11 03:38:29 4494 Initial revision (saved to drafts)