Блог пользователя c1729

Автор c1729, история, 6 лет назад, По-английски

In response to eatmore excellent blog post on the design flaws of Google's new Code Jam site, my brother and I created a simple UserScript to fix the recent UI changes.

You can use install it via Greasemonkey, Tampermonky, etc. with this link, or if you prefer, directly via the code from here.

  • Removed the useless graphs from the leaderboard.
  • Removed the editor from the problem page, and moved the submit button to the bottom.

Due to the fact that the page was designed to hold only half the question in the first place, split screening with a custom editor actually looks quite nice. I've attached some pictures below.

This is still a work in progress, and there might be some bugs, please feel free to send your feedback.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +94
  • Проголосовать: не нравится

Автор c1729, история, 6 лет назад, По-английски

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!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится