c1729's blog

By c1729, history, 11 months ago, In English,

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 and algorithms.

Python Version

Based on prior benchmarking on Codeforces, it is quite conclusive that PyPy 2 is the fastest version of Python available on Codeforces.

PyPy 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 case in Python 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 for specific types (integers and non-strings). The safest way to redefine input/print while maintaining the same functionality is to use the following code,

import os
import sys
from atexit import register
from io import BytesIO

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

if your input does not involve strings, you can directly use,

import os
import sys
from atexit import register
from io import BytesIO

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 lots of integers as input and would require custom str -> int.

You can also do much faster output in PyPy 2 by following pajenegod's instructions here.

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 range, filter, map, and zip all return iterators in Python 3 as opposed to lists in Python 2 and thus use less memory and are slightly faster when you don't need the data more than once.

A 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.

""" 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 give detail on how to resolve this issue. I've added some code below that should work for both. However, overall, this is much slower than using your own stack in Python.

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:
                call, arg = cont.switch(to=continulet(lambda _, f, args: f(*args), call, arg))

        cont = continulet(bootstrap)
        cont.switch()

        main()

    else:
        sys.setrecursionlimit(1 << 30)
        threading.stack_size(1 << 27)

        main_thread = threading.Thread(target=main)
        main_thread.start()
        main_thread.join()

Credits

The vast majority of the techniques listed are thanks to pajenegod and his repeated iterations.

Please feel free to message/mail me with your findings too!

 
 
 
 
  • Vote: I like it
  • +46
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Awesome and Thanks a ton :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by c1729 (previous revision, new revision, compare).

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You and Pajenegod ...both are awesome...I m a python programmer and I was searching people of python community...your repository of python coded algorithms are awesome..it makes my life quite easy...