Python-оптимизация алгоритма динамического программирования из codechef

Версия 01:18, 1 мая 2022

При разборе ваших решений, столкнулся с одной из попыток, с результатом «вроде все сделано правильно, но система не пропускает, наверно что-то не так с системой или вообще питон не потянет, вот на плюсах все решают и все хорошо».

Попробую кратко показать, как можно системно поработать с улучшением решения, даже не особо вьезжая в алгоритм (ну при условии, что идея будет правильна).

Первая версия digprime.py

Видим вроде типичный алгоритм ДП, смотрим описание задачи Codechef/DIGPRIME, переходим по ссылке Editorial на разбор и разъяснение задачи, но даже если этой ссылки не будет, смотрим список принятых решений:

Берем из них любое принятое CPP-решение, сохраняем его в файл digprime-good.cpp компилируем его

 gcc -g -o digprime-good digprime-good.cpp -lstdc++

Итак, у нас есть референсное решение.

Смотрим на описание задачи, особенно на секцию «ограничения»…

и пишем примитивных генератор «digprime-generate.py», такой, чтобы задействовать все ограничения (вдруг все проходит на минимальных данных, но где-то что-то переполняется на самых крайних случаях), плюс большой тестсет даст возможность разумно измерять время работы.

import numpy as np
num = 100000
print(num)
for t in range(num):
    print(np.random.randint(1,1000000000000000000))

Генерим наш тестовый набор:

python digprime-generate.py > big-samples.txt

Генерим результаты нашего алгоритма и референсной реализации на тех же входных данных:

digprime-good < big-samples.txt > reference-good.txt
python digprime.py < big-samples.txt > big-our-results.txt

Сравниваем («meld», «winmerge», «fc», ) — используйте то, что ставится на вашу ось и есть под рукой, но в данном случае, совпадение добайтовое даже по ответу «md5sum»:

md5sum big-our-results.txt
  e602cd2d36e9c6749764cace13774bdc  big-our-results.txt

md5sum reference-good.txt
  e602cd2d36e9c6749764cace13774bdc  reference-good.txt

Вроде же все в абсолютном порядке, но что выдает codechef?

Ошибка «NZEC» — «какая-то ошибка», увы, без малейших подсказок на чем, и что за ошибка. Но по времени работы — доли секунды, предположим, что что-то сразу с вводом.

Тут на самом деле наблюдались разные проблемы в этих (codechef, spoj) тестовых системах. То что-то не так с буферизацией, и какой-то перевод строки становился пробелом, или длинная строка, и input() не вычитывал ее до конца, то большое количество операций input, а там перенаправление на чтение из файла, много IO операций, срабатывают какие-то контейнерные ограничения или просто будет тормозить.

Поэтому, лучше сразу сделать чтение типа

    lines = sys.stdin.readlines()
    content = " ".join(lines).strip()

А потом парсить и отдавать результаты генератором.

Делаем такие правки и получаем

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

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

Ага, от NZEC уже избавились, но теперь здравствуй TL.

Может если перейти на PYPY, скомпилируется и пройдет?

Увы, нет.

Обращаю внимание — 10.01 и 4.01 секунды это не время работы программы! Это только таймлимиты (плюс сколько мгновений, пока программу не убили), которые выделены питону (Python 3.6) и скомпилированному питону (PYPY).

Хотя обычному питону дается фора, в 2.5 раза времени, выигрыш PYPY обычно бывает больше. Есть конечно минусы PYPY — в нем нет numpy, удобных многомерных массивов и эффективных матричных операций, есть модуль «array», который иногда полезен… но в нашем случае, попробуем обойтись без всего этого, используя обычные питоновые списки-вектора, структуры, которые были изначально.

А вот что необходимо — начать замерять время выполнения (экзаменационная система вам не поможет — там только да или нет), и профилировать выполнение.

У меня древний десктоп нулевых годов, цифры могут отличатся от ваших, если вы повторяете эксперименты, плюс у вас будут другие входные данные, но буду приводить свои данные. Обычная linux утилита time, где нужно смотреть только «user time» нам вполне подойдет.

time python digprime.py < big-samples.txt > big-our-results.txt

real    1m8.108s
user    1m6.412s
sys     0m0.351s

time pypy3 digprime.py < big-samples.txt > big-our-results.txt

real    0m4.519s
user    0m4.143s
sys     0m0.143s

Впечатляющая разница? Но нам увы, недостаточно.

Давайте посмотрим, что «жрет». Всегда можно сделать стандартное профилирование (разумная сортировка по общезатраченному времени «-s cumulative»)

python -m cProfile -s cumulative digprime.py < big-samples.txt >profile-results.txt

Что видно — огромное количество (43.5M) рекурсивных вызовов функции «calculate», ну и еще там где-то зря дергаются лишний раз «len()».

Начинаем оптимизировать.

CPython time → 41.203s Pypy time → 2.722s Вызовов calculate 26874678