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

Автор jhilary, история, 8 лет назад, По-русски

Написала код для задачи http://mirror.codeforces.com/problemset/problem/680/E (про медведя на клетчатом поле) на Python. Застряла на 12м тесте с вердиктом "Превышено ограничение времени на тесте 12". Попробовала максимально оптимизировать написаный код, но все равно не выходило пройти ограничение по времени. Запускала с помощью pypy2 (если запускать python2, то выходит в 6 раз медленнее).

Последняя попытка здесь: http://mirror.codeforces.com/contest/680/submission/18710430

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

Сдала с первой попытки: http://mirror.codeforces.com/contest/679/submission/18726182

  • 12й тест, который не проходил на pypy2 с ограничением времени в три секунды, прошел за 561ms.
  • 11й тест(предыдущий) прошел в с++ версии за время вдесятеро меньшее, чем на pypy2

Вопросы:

  1. Можно ли оптимизировать мой питоновский код, чтоб он таки прошел ограничение? При том, что 12й тест не самый тяжелый. В списке сдавших эту задачу нет ни одного питониста
  2. Почему ограничения на задачу выставлены таким образом, что абсолютно одинаковые решения на двух языках находятся в неравных условиях?

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

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

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Я, конечно, не эксперт по питону, но попробую ответить.

  1. Скорее всего, нет.
  2. Потому что если увеличить ограничения, то на C++ начнут проходить решения с более плохой асимптотикой, т. е. всё равно у C++ будет преимущество. Ограничение по времени не повлияет на то, что питон медленнее.

Пожалуй, единственный выход — не писать на питоне сложные задачи.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    1. Так выходит, что у меня еще ни одна задача на графах на питоне с первого раза не проходила по времени. Но раньше получалось в итоге оптимизировать код так, чтоб ограничения проходились: уменьшение числа используемых структур, отказ от туплов, отказ от двойной индексации, отказ от вспомогательных функций etc. В этой же задаче отказ от двойной индексации вылился бы в боль при реализации перемещения квадратика, может быть это и спасло бы

      • Медленность питона выливается в плохую константу. Но я, к сожалению, слабо представляю, как можно было бы оценивать эту константу оверхеда при разработке задач. Может можно реализовывать на плюсах и пытаться оценить как-то время расставляя множители оверхеда в операциях в зависимости от используемых структур и высчитывать результирующее время. Тогда можно было бы ставить время для разных языков свое. Но это какой-то глубокий анализ, и непонятно возможно ли такое сделать
      • Можно было бы сделать, например, более долгий тест (например, матричка не 500x500, а 800x800), где решение на плюсах с плохой асимптотикой все равно не проходило бы, а решение на питоне даже с такой константой проходило. Но опять же, хоть приблизительная оценка константы все равно нужна. И вполне возможно, что тогда тесты будут не по 3, а по 10 секунд, а это будет значить более долгое ожидание результата
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Понятна позиция. Пожалуй соглашусь. А насчет numpy нет обсуждения? Насколько я знаю, самая оптимальная реализация массивов и всякой математики именно там, а использовать эту библиотеку нельзя

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          Я обсуждений не видел.

          Моя мысли на этот счёт: языки C++ и Java являются де-факто "стандартными" в олимпиадах высокого уровня (в основном это идёт с ACM ICPC). В numpy помимо массивов есть ещё огромное количество всяческих полезностей, вроде линейной алгебры, быстрого преобразования Фурье, очень быстрого перемножения матриц и так далее. Это может дать очень существенное преимущество в некоторых задачах, более того — некоторые задачи таким образом можно будет сдать не тем методом, которые предполагали авторы. Скажем, свести какую-нибудь задачу к умножению матриц и подставить в numpy вместо того, чтобы честно придумывать какую-нибудь оптимизацию в динамике или смотреть на внутренность задачи. Наверняка внутри numpy есть ещё много чего, и думать при составлении задачи про всё сразу с точки зрения автора задачи довольно запарно. Я бы не стал разрешать numpy — мне кажется, это какой-то ещё более неравномерный перекос будет. Скажем, та же рекурсия на питоне наверняка будет продолжать тормозить.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

          Есть такое обсуждение.

          Если вкратце, используется принцип неиспользования сторонних библиотек, т. е. только то, что есть в языке по умолчанию.

»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Я привык считать, что питон в 1000 раз медленнее C++. Наверное, для PyPy можно сделать оценку 100. Это ОЧЕНЬ много. Просто катастрофически. Конечно, в теории алгоритм с лучшей асимптотикой на достаточно больших тестах будет быстрее. К сожалению, иногда такие тесты бывают настолько большими, что и оптимальный алгоритм будет работать на них больше сотни лет. Поэтому константный фактор нельзя просто так опускать при рассуждениях. В конце концов, цель же не доказать асимптотику, а сдать задачу.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Соглашусь, нужно изначально оценить сложность и научиться прикидывать константу до выбора языка реализации. Наверное, так и буду поступать. Была мысль, что буду все задачи на питоне писать. Но теперь придется пересмотреть эту мысль и учиться писать быстро на плюсах или джаве. Думаю, что все-таки для pypy соотношение не 100 к 1, а примерно 10 к 1. Это я исхожу из наблюдений к этой задаче, и что все-таки для других задач на графах я таки вкладывалась во время 1.5 секунды и максимальное время на тест было все же не в 100 раз больше максимального времени у среднего решения на плюсах.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Есть такая известная оптимизация: a[i][j] хранить как a[i*m + j]. Но не факт что поможет.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Да, верно, я эту оптимизацию использовала для более простых задач на графы, и это дает ускорение в полтора раза. Решение тех задач не проходило по времени, но благодаря в том числе и замене на такой вид индексации удавалось добиться того, что задачи начали проходить.

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

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