Python-оптимизация алгоритма динамического программирования из codechef
При разборе ваших решений, столкнулся с одной из попыток, с результатом «вроде все сделано правильно, но система не пропускает, наверно что-то не так с системой или вообще питон не потянет, вот на плюсах все решают и все хорошо».
Попробую кратко показать, как можно системно поработать с улучшением решения, даже не особо вьезжая в алгоритм (ну при условии, что идея будет правильна).
Видим вроде типичный алгоритм ДП, смотрим описание задачи 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
| ncalls | tottime | percall | cumtime | percall | filename:lineno(function) | ||
|---|---|---|---|---|---|---|---|
| 1 | 0.000 | 0.000 | 103.393 | 103.393 | {built-in | method | builtins.exec} |
| 1 | 2.716 | 2.716 | 103.393 | 103.393 | digprime.py:2(<module>) | ||
| 43546528/100000 | 93.691 | 0.000 | 100.071 | 0.001 | digprime.py:19(calculate) | ||
| 43546528 | 6.380 | 0.000 | 6.380 | 0.000 | {built-in | method | builtins.len} |
Что видно — огромное количество (43.5M) рекурсивных вызовов функции «calculate», ну и еще там где-то зря дергаются лишний раз «len()».
Начинаем оптимизировать, учитываем пропущенную эвристику[1], делаем правку, получаем версию, для которой
CPython time → 41.203s Pypy time → 2.722s Вызовов calculate → 26874678
Уберем кстати, хардкодинг, число цифр в константу.
делаем правку, получаем версию, для которой
CPython time → 40.610s Pypy time → 2.749s Вызовов calculate → 26874678
(ничего интересного не достигли)
Введем глобальную переменную N c длиной текущего числа, уберем перерасчитывание высчитывание длины
внутри функции.
… делаем правку, получаем версию, для которой …
CPython time → 37.117s Pypy time → 2.907s Вызовов calculate → 26874678
… чуть ускорили обычный питон, где байткода такие вещи не оптимизирует, но скомпилированный PyPy лучше не стал.
Потом в коде видим странные штуки типа «taken | (x == 2) | (x == 3) | (x == 5) | (x == 7)» — ох тыж, считается «бинарное или» вместо логического, а ведь в везде «логическое или» оптимизируется слева направо, т.е. если левый операнд уже «истина», то дальше ничего считать не надо.
… делаем правку, получаем версию, для которой …
CPython time → 24.413s Pypy time → 2.907s Вызовов calculate → 26874678
Большой прорыв по обычному питону, но PyPy3 об этом похоже, догадался сам, тут не помогло.
Небольшие правки, вроде убираем ненужные требования о преобразованиях типов
… если и есть экономия, то копеечная.
Пора заняться важным, оптимизацией хвостовой рекурсии.
Мы видим, что в рекурсивной функции, в самом начале у нас куча эвристик по выходу из этой функции… так может ее сразу не вызывать в рекурсивных вызовах? А в первом вызове они не сработают.
Начинаем, переносить каждое условие по одному
… экономия начинает появлятся, хотя во времени на уровне колебаний измерения, но вот количество рекурсивных вызовов уменьшилось:
CPython time → 24.718s Pypy time → 2.413s Вызовов calculate → 25324715
Переносим «эвристику с десятками»
радикально уменьшились рекурсивные вызовы (хотя внутри функции теперь больше работы), но время тоже падает
CPython time → 21.763s Pypy time → 2.270s Вызовов calculate → 11972222
Переносим «кеширование DP»
радикально уменьшились рекурсивные вызовы (хотя внутри функции теперь больше работы), но время тоже падает
CPython time → 17.762s Pypy time → 2.099sВызовов calculate → 3477870
- ↑ что когда у нас «230» → то на второй цифре можно сразу вернуть число десятков, не перебирая глубже
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.