M Cr@$h

Тема: Python и участие в олимпиадах по программированию. Всё ликвидо теперь. Беседуем.

Добавлено @ 13:23 

Там обычно последний тест -- как раз на скорость дают. Часто заваливает.

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

Java слишком многословна в алгоритмических задачах, которые обычно предлагаются на олимпиадах.

На мой взгляд, как раз наоборот. Питон отстаёт в скорости от C++ в среднем на порядок, поэтому правильный, но не «вылизанный» алгоритм с той же асимптотикой может пролететь.
А вот потребление памяти отличается не так сильно и рамки обычно задают чисто символические, так что при минимальной аккуратности в реализации выйти за них трудно.

Кстати, на Google Code Jam Python есть в списке доступных языков.

для тех кто не знает - на порядок это в 10-ть раз!

У программистов — может быть ещё и в два раза  А может в e?
Знаю, что в десять, и именно эту цифру имел в виду. Шустрики проводить будем? Интерпретатору байт-кода без JITа с нативно компилируемым языком не тягаться, это бессмысленно даже обсуждать.
Для затравки: Python vs GCC (знаю, знаю, более дурацких бенчмарков, чем на этом сайте, в природе нет, но и такого широкого охвата тоже нигде не найти).
Исключение: можно получить даже некоторое превосходство в программах, большую часть времени проводящих в функциях стандартной библиотеки, например, dict vs std::map или длинная арифметика Питона vs самопальная.

Да, я тоже присоединяюсь к этому высказыванию. Иногда за дебрями синтаксиса можно и суть потерять. Плюс Python позволяет фнуциональный стиль, а это, батеньки, декларативное программирование, как мы все прекрасно знаем. Тут все преимущества и так понятны. Тем не менее в индустрии Java заняла прочные позиции и её синтаксис, объектная концепция пришлись весьма по вкусу программистам

В 10 раз это не сильно. Если алгоритм построен правильно и имеет сложность на O(N!), а O(N^10), то такие мелочи не повлияют на ход теста сильно, и он пройдёт успешно (про тест на олимпиадах говорю).

Возможно, но в С++ её можно полностью контролировать, а Python любит копии списков плодить (уже говорили).

Да, это факт. С другой стороны, сопосталяя с Java, в последней очень серьёзно представлены различные структуры данных. Это её козырь, без сомнений.
Мы так и не выяснили: функциональные языки допускают на российских олимпиадах?
И ещё один возник из этого обсуждения: разрешено ли использовать стандартные библиотеки? Я в первую очередь здесь имею в виду Java с её структурами. Или есть какие-нибудь ограничения?

Например? Открываю доку и смотрю содержимое java.util.*: списки, связанные списки, множества, словари, очереди. В Питоне это всё есть, кроме связанного списка (довольно быстро изображается вручную) и словарей/множеств с гарантированным порядком элементов (тут согласен, быстро и эффективно не напишешь, а иногда нужно).

Есть очевидные ограничения на I/O и прочие системные функции, связанные с безопасностью, но про ограничения на алгоритмы и структуры данных не слышал ни разу.

Не встречался с тем, чтобы это делалось скрытно от программиста. Т.е., вызывая какую-либо функцию, обычно имеешь чёткое представление, работает она in-place или создаёт копию.
Я повидал олимипдного кода на C++, написаного чудовищно неэффективно (передача std::string по значению и т.п.). Питон позволяет достичь сопоставимых результатов при существенно меньшем количестве нюансов, которые надо знать.
По моему скромному опыту на ICPC, ограничения на память обычно завышены относительно разумных требований гораздо больше, чем время выполнения, так что превысить их надо постараться.

Сильно зависит от конкретной задачи. Я могу представить ситуацию, когда при идентичных алгоритмах код на C++ впишется в рамки, а на Питоне — нет.

Да, это из той же серии: иногда в библиотеках реализованы полезные вещи 

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

В точку. Цель не оправдывает средства (или даже наоборот тоже верно будет).

Хорошо, что там может тормозить так? Интерпретируемость? У Java в этом смысле проблем поменьше, там разработчики стараются над каждой версией оптимизировать. И если дело в этом, есть ли реализации Python для байт-кода? Типа JRuby, что ли.

Я понял, просто несколько неудачно выразился  Именно про ограничения на использование стандартных библиотек не слышал. STL использовали без ограничений, чем Java хуже.

Java может JIT-компилироваться. Питон — только интерпретируется.

Jython. Но, во-первых, в смысле языка Jython остановился на уровне CPython 2.1. Во-вторых, использование байткода JVM вместо байткода виртуальной машины Питона не означает автоматическое улучшение производительности. Питон — динамический язык, и для его эффективного исполнения нужны значительные усилия по анализу кода, выводу типов и оптимизации. Я сам Jython не использовал, так что было бы интересно, если бы кто-то просветил по поводу его быстродействия относительно CPython и Java.

Тогда full trottle!

Именно это и позвроляет ей работать "чуть" быстрее.  

Присоединяюсь. И мне интересно. Возможно, по скорости он "прилично" быстрее Python. Конечно, мы это из разговора об олимпиадах и применению на них (быстрого/небыстрого) Python вывели. Может, подспорье будет...

Вот это жалко. Возможно, не прижился таки. Своя машина и так есть.

Добавлено @ 01:17 
Приветствую Void в обсуждении. Что так заходишь поздно? Дел, наверное, много. У тебя какое местное время было?

Это сообщение отредактировал(а) Cr@$h - 13.9.2006, 01:18

Мда ну и написали за время моего отсутствия! Ладно, начну по порядку.
Любая задача может делиться на несколько категорий, таких как память, скорость, алгоритм и смешанные.

Про память:
Ну допустим есть такая простая задачка. есть 1000000 чисел от 0 до 100. Памяти разрешено 2 Мб. Уместит ли питон такой массив в том количестве памяти?
На сколько я понимаю любые функции функционального программирования пораждают новые списки, что может сильно использовать память.
Но в случае чего можно не полагаться на сборщик мусора, и самим отчищать использованную память.

Про скорость:
Основная загводзка скорости будет состоять в обработке списков, или переборе. В первом случае у питона есть встроенные функции, написанные на си, так что с этим особых проблем может и не быть, а перебор можно таким-же образом перевести в списковую структуру, и его обрабатывать. К тому-же есть множества, разрешающие использовать чуть ли бесконечное количество элементов.

Про ограничения на программу:

Кроме перечисленных ограничений, могут также встречаться и алгоритмические ограничения, но это в основном на классические языки. Как например, чтобы код программы умещался в 200 символов, или программа должна быть линейной. 
Есть такой классический пример - надо отсортировать массив положительных чисел, причем программа должна быть линейной. Для питона еще могли бы сделать ограничение, что нельзя пользоваться функцией sort, множествами и любыми логическими операциями.


В любой олимпиаде организаторы заранее говорят, что программу можно написать на любом предоставленном языке, и она может пройти все тесты.


Бред. Если посмотреть, то даже у си есть такие библиотеки как vector и algorithm, в которых очень многое реализованно.

Добавлено @ 09:07 

Возможно есть, но это олимпиады не широкого масштаба. Я несколько встречал, в которых допустимых языков было достаточно много.
На ACM разрешено использовать только 3 - Pascal (Delphi), C++ (Visual C++.NET), Java. Но в финале уже убрали паскаль, т.е. оставили всего два языка. Так что надежда на появление там питона ОЧЕНЬ мала.

проверил на скорость:



         4 function calls in 0.066 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.040    0.040    0.040    0.040 (range)
        1    0.000    0.000    0.000    0.000 (setprofile)
        1    0.026    0.026    0.066    0.066 <string>:1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.066    0.066 profile:0(range(0, 10**6, 1))


Как проверить на использумую память?

Да, но раз

то я бы разрешал всё. Если Python помогает лучше решать олимпиадные задачи, то пускай другие языки пеняют на себя.

Кстати, я ошибся, в той программе могут быть всего 2 цикла, а все остальное линейно и без логических операций.
Кому не слабо, пусть попробует выложить. Естестно на питоне, и чтоб все честно было.

Не понял, сам смысл сортировки же это расположение некоторого множества элементов в соответствии с некоторым порядком, определенным на элементах. А порядок - это функция, определенная для пар элементов, возвращающая логическое значение.
С другой стороны, если все завязано на положительности и целых чисел, как элементов упорядочиваемого множества, так все равно, можно попытаться завязать на проверке равенства нулю в ходе ряда действий, что также есть логическая операция...
Эх, старею что-то 

Какой-то школьный уровень, право слово  Однако придётся поверить, что и такое встречается.

Во-первых, мы рассматриваем гипотетический случай, поскольку о реальном применении Питона на олимпиадах пока никто не сообщил. Во-вторых, на упомянутом Google Code Jam было открыто сказано, что некоторые задачи возможно нельзя будет решить на Питоне из-за ограничений по времени выполнения.

Так кто заставляет использовать Питон, как чисто функциональный язык?

Массив — уместит (см. модуль array). Но в ограничения не впишется, потому что только его рантайм займёт сразу после загрузки программы существенно больше памяти.