IlyaCk's blog

О быстродействии Python на олимпиадных проверялках
By IlyaCk, history, 5 years ago, In Russian

Заранее прошу прощения, если вопрос быстродействия Python на олимпиадных проверялках где-то уже обсуждался достаточно подробно и относительно недавно; в таком случае, прошу указать места таких обсуждений.

Сразу уточню, что вопрос меня интересует не столько в применении к CF, сколько в разрезах "как правильно настраивать ту копию ejudge, которую я со-админю" и "что делать мне как тренеру, когда есть ученики, которые лучше всего знают Python (и непонятно, стОит ли заставлять/убеждать их выучить C++), которых надо хоть как-то подготовить к вряд ли победному, но хоть не слишком провальному выступлению на некоем (скажем, областном) туре, проводимом на централизованном (не моём) сервере".

По моим наблюдениям, В_СРЕДНЕМ Python оказывается медленнее C++ в 1,2--3 раза, и это относительно терпимо, если ставить time limit в 3--5 раз выше времени авторского решения.

Однако, ИНОГДА (в частности, в задачах, где очень-очень много используется операция %, называемая также mod) Python оказывается медленнее C++ в добрых 10--20 раз. Увеличивать TL аж настолько я не_хочу, даже когда имею такую административную (техническую) возможность. (Или, может, дело не в mod... Если кто-то (значительно более, чем я, шарящий) захочет помочь, начиная с выяснения первопричины -- дам права на своей копии ejudge; judge set -- вообще без проблем, более глубокие -- смотря по обстоятельствам.)

Настолько резкие проседания на конкретных задачах -- они вообще лечатся на стороне сервера? Если да, то как? (вроде есть какой-то специальный Python? Кажется, pypy? А он нормально взаимодействует с ejudge? есть какие-то особенности, которые надо изучить перед тем, как его ставить?) И принято ли их лечить на именно тех серверах, которые используются на украинских областных (в централизованном варианте) и финальных этапах? (Не_окажутся ли усилия по нивелированию этой проблемы на нашем сервере жесточайшей медвежьей услугой тем участникам, которые потом будут писать на другом сервере?)

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

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

A little bit off topic:

Once I was interested how to speed up python and googling something like "how to speed up python" helped to learn some basic rules (this is not the link I found back than) like:

  • do not += string
  • do not reinvent wheel
  • keep namespace clean
  • high order functions sometimes work faster than loops

Following this gave another insignificant 0.01 improvement over previous result.

IMHO people who use python for CP should make sure they know basic differences between Py3 and Py2 (e.g. never in Py2 

for i in range(10**9): 
 if i % 2 == 0:
    break

)

The main problem with p̶a̶s̶c̶a̶l̶ python to my mind is absence of STL, in UOI probably it is less significant but in ACM it is crucial. On the other hand, long arithmetics in PY3 is for free.
And in some regions of ACM ICPC judges provide solutions in python, so looks like it is starting to be trendy in CP also. Another interesting thing is that Kotlin is also fast to write, though slow to work.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Володя, а ты серьёзно считаешь, что все эти нагромождения join-ов, map-ов и filter-ов того стОят? (Изучать именно их, а не более быстрый язык программирования?) Кстати, спрашиваю вполне серьёзно.

    А есть ли у тебя какое-то мнение о том, стОит ли рассматривать это всё на "классическом" Python, или на pypy? (Хотя, вряд ли ты знаешь, куда сейчас дрейфует UOI, а нужный мне ответ может зависеть в т.ч. и от этого.)

    И, чтоб быть уверенным, что мы говорим в рамках одной терминологии: high order functions — это в смысле Python Higher-Order Functions and Decorators A function can take one or more functions as arguments. A function can be returned as a result of another function.? Или каком-то другом?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      На счёт изучать быстрые языки программирования — наверное зависит больше от потребностей рынка труда. Почти весь Data Science на Python оттуда, наверное, и его популярность. Ну а знать подводные камни и особенности языка на котором работаешь, думаю, так же важно как и структуры данных, тем более что это взаимосвязанно. В любом случае, если нет времени/желания/возможности учить С++ с 0, наверное, стоит хотя бы прочитать 1-2 статей в интернете как писать код на Python так, что-бы он не бежал вечность.

      Не знаю куда дрейфует UOI, но если не в сторону PyPy то, нужно будет видать делать разные TL на разных языках (как на некоторых ресурсах).

      Да, higher order functions, на С++ они тоже есть, не знаю на сколько популярны в СП.

      → Reply