Python-оптимизация жадного алгоритма из codechef

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 9 промежуточных версий этого же участника)
Строка 5: Строка 5:
 
{{oldid|1=chefstr2.py|2=20542|3=Первая версия}}  
 
{{oldid|1=chefstr2.py|2=20542|3=Первая версия}}  
  
Видимо легкий перебор, два-три вложенных цикла (три цикла, что-то дофига, причем два тут явно с зависимостью от длины входа — не к добру), что-то считается, что-то отбирается по максимуму…,  суммируется, отбирается по минимуму — типичный жадный алгоритм.
+
Видимо легкий перебор, три вложенных цикла (три цикла, что-то дофига, причем явно с зависимостью от длины входа — не к добру), что-то считается, что-то отбирается по максимуму…,  суммируется, отбирается по минимуму — типичный жадный алгоритм.
  
 
Cмотрим описание задачи [[Codechef/CHEFSTR2]], даже сразу  переходим по ссылке [https://discuss.codechef.com/t/chefstr2-editorial/83721 на разбор и разъяснение].
 
Cмотрим описание задачи [[Codechef/CHEFSTR2]], даже сразу  переходим по ссылке [https://discuss.codechef.com/t/chefstr2-editorial/83721 на разбор и разъяснение].
Строка 15: Строка 15:
 
Вот, нарисовал картинку в терминах исходной версии программы:
 
Вот, нарисовал картинку в терминах исходной версии программы:
  
[[File:chefstr2.svg|800px|center]]
+
[[File:Python-оптимизация жадного алгоритма из codechef_2022-05-05_12-39-25_image0.png|center|800px]]
 +
<!-- [[File:chefstr2.svg|800px|center]] -->
  
 
Мы можем попробовать делать циклы из подстрок разной длины («ind»), повторяющиеся разное число раз «ks», чтобы получилась строка, нужной длины или чуть длиннее (не больше чем на «ind»).
 
Мы можем попробовать делать циклы из подстрок разной длины («ind»), повторяющиеся разное число раз «ks», чтобы получилась строка, нужной длины или чуть длиннее (не больше чем на «ind»).
Строка 119: Строка 120:
 
Для очистки совести  
 
Для очистки совести  
 
{{diff| 20557 | уберем хардкод на 26 символов и прочтем входную строку через sys.readline}} — {{@|26.6}} стало даже чуть хуже, но вроде это более надежный ввод, если запускать на серверах кодечифа.
 
{{diff| 20557 | уберем хардкод на 26 символов и прочтем входную строку через sys.readline}} — {{@|26.6}} стало даже чуть хуже, но вроде это более надежный ввод, если запускать на серверах кодечифа.
 
 
https://discopal.ispras.ru/index.php?title=Chefstr2.py&oldid=20557
 
  
 
Что еще напрягает? Ну вот зачем такие глубокие косвенности:
 
Что еще напрягает? Ну вот зачем такие глубокие косвенности:
 
   frequency[symbols[(input_str[j])]]
 
   frequency[symbols[(input_str[j])]]
  
Давайте сразу переведем строку в индексы символов,
+
* Давайте {{diff| 20559 | сразу переведем строку в байт-массив индексов символов, и будем работать с ним }} → {{!|13.7}} — почти в два раза!
 
+
https://discopal.ispras.ru/index.php?title=Chefstr2.py&oldid=20555
+
 
+
{{oldid|1=chefstr2.py|2=20468|3=версию, которая работает абсолютно также}} по результату, возможно
+
 
+
 
+
 
+
 
+
 
+
А потом парсить и отдавать результаты генератором.
+
 
+
Делаем {{diff| 20478 | такие правки}} и получаем
+
 
+
 
+
{{oldid|1=digprime.py|2=20468|3=версию, которая работает абсолютно также}} по результату, возможно чуть медленней перекопированием ввода в память (если померять у себя), но возможно быстрее, чем у них на сервере, с задушенным IO.
+
 
+
В любом случае, сначала надо избавиться от NZEC, потом уже заниматься оптимизацией.
+
 
+
[https://www.codechef.com/viewsolution/63961222 Ага, от NZEC уже избавились],
+
но теперь здравствуй TL.
+
 
+
[[File:Python-оптимизация алгоритма динамического программирования из codechef_2022-05-01_03-36-58_image0.png||400px]]
+
 
+
Может если [https://www.codechef.com/viewsolution/63961211 перейти на PYPY], скомпилируется и пройдет?
+
 
+
Увы, нет.
+
 
+
[[File:Python-оптимизация алгоритма динамического программирования из codechef_2022-05-01_03-34-48_image0.png||400px]]
+
 
+
Обращаю внимание — 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
+
 
+
<tab head=top border=1 sep="spaces" cellspacing=5 class="wikitable">
+
  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}
+
</tab>
+
 
+
Что видно — огромное количество (43.5M) рекурсивных вызовов функции «calculate», ну и еще там где-то зря дергаются лишний раз «len()».
+
 
+
Начинаем оптимизировать, учитываем [https://discuss.codechef.com/t/digprime-editorial/13433 пропущенную эвристику]<ref>что когда у нас «230» то на второй цифре можно сразу вернуть число десятков, не перебирая глубже</ref>,
+
делаем  {{diff|20497|правку}}, получаем {{oldid|1=digprime.py|2=20497|3=версию}}, для которой
+
 
+
CPython time → 41.203s
+
Pypy time → 2.722s
+
Вызовов calculate → 26874678
+
 
+
Уберем кстати, хардкодинг, число цифр в константу.
+
 
+
делаем  {{diff|20499|правку}}, получаем {{oldid|1=digprime.py|2=20499|3=версию}}, для которой
+
 
+
CPython time → 40.610s
+
Pypy time → 2.749s
+
Вызовов calculate → 26874678
+
 
+
(ничего интересного не достигли)
+
 
+
 
+
Введем глобальную переменную N c длиной текущего числа, уберем перерасчитывание высчитывание длины
+
внутри функции.
+
 
+
 
+
… делаем  {{diff|20501|правку}}, получаем {{oldid|1=digprime.py|2=20501|3=версию}}, для которой …
+
 
+
CPython time → 37.117s
+
Pypy time → 2.907s
+
Вызовов calculate → 26874678
+
 
+
… чуть ускорили обычный питон, где байткода такие вещи не оптимизирует, но скомпилированный PyPy лучше не стал.
+
 
+
Потом в коде видим странные штуки типа «taken | (x == 2) | (x == 3) | (x == 5) | (x == 7)» ох тыж, считается «бинарное или» вместо логического, а ведь в везде «логическое или» оптимизируется слева направо, т.е. если левый операнд уже «истина», то дальше ничего считать не надо.
+
 
+
… делаем  {{diff|20502|правку}}, получаем {{oldid|1=digprime.py|2=20502|3=версию}}, для которой …
+
 
+
CPython time → 24.413s
+
Pypy time → 2.907s
+
Вызовов calculate → 26874678
+
 
+
Большой прорыв по обычному питону, но PyPy3 об этом похоже, догадался сам, тут не помогло.
+
 
+
Небольшие правки, вроде убираем ненужные требования о преобразованиях типов
+
<blockquote>
+
… делаем  {{diff|20503|правку}}, получаем {{oldid|1=digprime.py|2=20503|3=версию}}, для которой …
+
</blockquote>
+
… если и есть экономия, то копеечная.
+
 
+
----
+
 
+
Пора заняться важным, оптимизацией хвостовой рекурсии.
+
 
+
Мы видим, что в рекурсивной функции, в самом начале у нас куча эвристик по выходу из этой функции… так может ее сразу не вызывать в рекурсивных вызовах? А в первом вызове они не сработают.
+
 
+
Начинаем, переносить каждое условие по одному
+
<blockquote>
+
… делаем  {{diff|20504|правку}}, получаем {{oldid|1=digprime.py|2=20504|3=версию}}, для которой …
+
</blockquote>
+
… экономия начинает появлятся, хотя во времени на уровне колебаний измерения, но вот количество рекурсивных вызовов уменьшилось:
+
 
+
CPython time → 24.718s
+
Pypy time → 2.413s
+
Вызовов calculate → 25324715
+
 
+
Переносим «эвристику с десятками»
+
<blockquote>
+
… делаем  {{diff|20505|правку}}, получаем {{oldid|1=digprime.py|2=20505|3=версию}}, для которой …
+
</blockquote>
+
радикально уменьшились рекурсивные вызовы (хотя внутри функции теперь больше работы), но время тоже падает
+
 
+
CPython time → 21.763s
+
Pypy time → 2.270s
+
Вызовов calculate → 11972222
+
  
Переносим «кеширование DP»
+
* Давайте {{diff| 20562 | не уныло обнулять вектор частот, а сразу выделять новый забитый нулями }} {{!|13.1}}.
<blockquote>
+
… делаем  {{diff|20506|правку}}, получаем {{oldid|1=digprime.py|2=20506|3=версию}}, для которой …
+
</blockquote>
+
радикально уменьшились рекурсивные вызовы (хотя внутри функции теперь больше работы), но время тоже падает
+
  
CPython time 17.762s
+
* Попытка {{diff| 20564 | поставить более вероятную ветку в первый «if» не помогла }} {{@|13.1}}.
Pypy time → 2.099s
+
Вызовов calculate → 3477870
+
  
Явно улучшилось!
+
* А вот континтуитивное — {{diff| 20567 | заменяем стандартный поиск максимального элемента на корявое поддержание «максимальной текущей частоты»}} → {{@|9.3}}. Тут выигрыш скорее всего за счет того, что на «длинных путях» у нас массив частот становится разряженным, и максимальную частоту дешевле считать так, чем бегать по всему массиву.
 +
* А может, если у нас чувствуется разряженность, {{diff| 20569 | перейти с списка частот на хеш?}} → {{@|13.4}}. Не помогает, стало хуже.
  
Да, тут многое чешеться еще улучшить, но пора попробовать, вдруг уже пройдет →  
+
Пора подумать внимательно, зачем нам так много нужно вложенных циклов.
[https://www.codechef.com/viewsolution/63961917 ура, проходит]!  
+
* Внешний цикл по длинам подстрок — ладно, пусть остается.
 +
* А два внутренних — по сути, подсчет «частот символов на разноцветных путях», и расчет из этого количества операций. Давайте заменим это на один цикл, по самой строке (вернее по массиву индексов символов), и для каждого индекса, будем решать, частоту какого символа (из «lenalf» символов) и на каком «пути» (из «ind» возможных путей) он увеличивает. {{diff| 20571 | Заводим списки векторы frequency — по сути, двухмерный массив, который моделируем одномерным списком, и массив max_frequency}} {{!|9.1}} удивительно! Выигрыш есть, но совсем небольшой. А ведь еще мы память тратим, но вроде тут она бесплатна<ref>Не надо так весело разбрасываясь памятью оптимизировать в продакшне реальных проектов, если действительно этот размен не будет оправдан!</ref>.
 +
* {{diff| 20573 | От огорчения убрал sys и вернул input }} — не повлияло.
  
[[File:Python-оптимизация алгоритма динамического программирования из codechef_2022-05-01_05-40-36_image0.png|center|640px]]
+
Пробуем загрузить решение в СС → увы, [https://www.codechef.com/viewsolution/64250087 TL]
  
Да, тут многое можно было написать красивей<ref>жалко, что пришлось вставлять лишний парсинг входа, с точки зрения чистых алгоритмов это конечно хак, хотя в любом случае это читаемый код, а не С++шный «лишбыработало» [https://www.codechef.com/viewsolution/14955997], [https://www.codechef.com/viewsolution/15415158])</ref>, очень желательны комментарии для будущих читателей кода… но для целей иллюстрации, как оптимизировать питоновский код, думаю, достаточно, чтобы не перегружать статью!
+
Ночь, хочеться спать.... и тут оживают Дьявольские Советы Черного Программиста → стоит подумать — а в чем практическая задача нашего кода?
  
Удивительно, что один из наших студентов решил [https://www.codechef.com/viewsolution/64117884 эту задачу на на CPython], хотя это конечно хак, запускать питоном чистый ассемблер!
+
Пройти приемочные испытания! Показать себя хорошо на реальных входных данных.
Не надо так делать в наших задачах, лучше подумать над алгоритмом, но всеже тема интересная и попробуем написать про такой подход статью-заметку.
+
Будут ли среди них такие плохие данные, ради которых стоит перестраховываться и увеличивать перебор? (по сути, можно считать, мы исследуем переход к вероятностным алгоритмам или «эффективности для почти всех исходных данных»).
  
 +
* {{diff| 20575 | Подкручиваем-уменьшаем перебор! }} — и наше [https://www.codechef.com/viewsolution/64250125 решение подходит], даже с хорошим запасом!
  
 +
Возможно конечно когда-нибудь в этой задаче дополнят тест-сет, и это решение не пройдет… так что оставим как челлендж на «отл» (при условии, что есть «одна теоретическая задача») →
 +
* сделать питон решение (без машинных кодов), которое проходит тесты, но перебирет все циклы до 0.75*n
 +
** ну либо обосновать, что действительно, можно опустить верхнюю оценку максимальной длины цикла в переборе.
  
 +
Челледж на «хор» → подобрать входные данные, на которых [https://www.codechef.com/viewsolution/64250125 вот это решение даст неправильный результат].
 +
{{wl-publish: 2022-05-05 00:01:56 +0000 | StasFomin }}
  
 
----
 
----
{{wl-publish: 2022-05-01 02:48:25 +0000 | StasFomin }}
 

Текущая версия на 09:39, 5 мая 2022

Продолжим тему Blog:Advanced Algorithms/Python-оптимизация алгоритма динамического программирования из codechef.

Итак, снова решение, которое вроде как работает, но не проходит по времени и жалобы, что питон плохой «Получаю TimeLimit в системе. Мне кажется, это связано с тем, что использую питон и в решении очень много численных операций а так как в питоне используются BigInteger BigFloats, то решение замедляется».

Первая версия

Видимо легкий перебор, три вложенных цикла (три цикла, что-то дофига, причем явно с зависимостью от длины входа — не к добру), что-то считается, что-то отбирается по максимуму…, суммируется, отбирается по минимуму — типичный жадный алгоритм.

Cмотрим описание задачи Codechef/CHEFSTR2, даже сразу переходим по ссылке на разбор и разъяснение.

Разьяснение немного мутное, и мутность там даже зачем-то подмешивается во входные данные (вторая строчка входа не нужна).

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

Вот, нарисовал картинку в терминах исходной версии программы:

Python-оптимизация жадного алгоритма из codechef 2022-05-05 12-39-25 image0.png

Мы можем попробовать делать циклы из подстрок разной длины («ind»), повторяющиеся разное число раз «ks», чтобы получилась строка, нужной длины или чуть длиннее (не больше чем на «ind»).


Рассмотрим строку «ABCABCAB».

Если делать цикл из одного символа («ind=1, ks=8»), то на «пути» (красным) надо посчитать частоты символов, выбрать самый частый (пусть он остается), остальные поменять на него — оптимальное жадное решение. Тут можно выбрать «А» или «B» и получить или . Сколько операций переименования-добавления? Это будет «len» символов новой строки с повторами, минус те символы, которых мы не переименуем («ok», три символа «A» или «B»). Будет 5 операций. (Если оставлять «C», то их будет 6, не подоходит).


Если делать цикл из двух символов («ind=2, ks=4»), то у нас уже возникают «красный» и «синий» путь — пути для первого и второго символа, на этих путях должны быть одинаковые символы, они совсем независимы, надо на каждом пути посчитать какой символ наиболее часто встречается, и переименовать все остальные в него.


На красном пути — самый частый → «A», на синем → «B». Значит, на «красном» пути оставим «A», остальных переименуем в него, на «синем» → «B». На обоих путях одинаково число оставляемых символов «ok1=2», «ok2=2» → число операций

ops = len - ok1 - ok2 = 8 - 2 - 2 = 4



Если делать цикл из трех символов («ind=3, ks=3»), то у нас уже возникают «красный», «синий» и зеленый пути — пути от первого, второго и третьего символа … … обратите внимание, что зеленый путь выходит за пределы исходной строки, т.е. один символ по любому придется добавить, ведь длина зацикленной строки «len = ks*ind = 9» больше длины исходной строки («8»).

На красном пути — самый частый → «A», на синем → «B», на зеленом → «С» Значит, на «красном» пути оставим «A», остальных переименуем в него, на «синем» → «B», на зеленом → «С».

ops = len - ok1 - ok2 - ok3 = 9 - 3 - 3 - 2 = 1

можно продолжать дальше, в разъяснении написано, почему «ind» не обязательно перебирать до исходной длины строки, идея понятна, у меня кончились красивые цвета для путей.

Разумеется, из всех вариантов циклов с разной длинной надо будет выбрать тот, где «ops» — минимально.


Итак, поехали. Пишем генератор тестовой строки

import random
import string
 
print(''.join((random.choice(string.ascii_letters).lower() for i in range(16000))))
print(1)

генерим «big-sample-04.txt» на 16K символов, берем референсный CPP-код из разъяснения, компилируем.

  gcc -o good good.cpp -lstdc++ -g
$ time good < big-sample-04.txt
7671 2

real    0m47.380s
user    0m46.872s
sys     0m0.053s

Работать будем сразу с PyPy3, не будем тащить numpy, какие-нибудь хитрые модули подсчета, и даже не будем использовать Counter из collections, хотя он сюда и напрашивается.

$ time pypy3 chefstr2.py  < big-sample-04.txt
7671 2

real    0m26.806s
user    0m26.286s
sys     0m0.104s

26.2 секунды.

Вау, забавно. Это решение вроде как копия референсного на CPP, а на PyPy работает быстрее. Но по TL не проходит!

Нет, пока чудес не бывает. Компилим CPP код с оптимизацией

gcc -o good good.cpp -lstdc++ -O3

и после этого наконец-то сишное решение показывает скорость:

$ time good < big-sample-04.txt
7671 2

real    0m1.968s
user    0m1.947s
sys     0m0.006s

Итак, правильное решение знаем, можем проверить, есть куда стремится по скорости. Первое, что напрягает — зачем нам тут модуль «math», вещественные числа (ересь! у нас тут честная комбинаторика). Только для того, чтобы округлять вверх? Это можно делать не выходя из целых чисел.


Делаем такие правки и получаем версию работающую за 24.5 — чуть лучше.

Для очистки совести уберем хардкод на 26 символов и прочтем входную строку через sys.readline26.6 стало даже чуть хуже, но вроде это более надежный ввод, если запускать на серверах кодечифа.

Что еще напрягает? Ну вот зачем такие глубокие косвенности:

 frequency[symbols[(input_str[j])]]

Пора подумать внимательно, зачем нам так много нужно вложенных циклов.

Пробуем загрузить решение в СС → увы, TL

Ночь, хочеться спать.... и тут оживают Дьявольские Советы Черного Программиста → стоит подумать — а в чем практическая задача нашего кода?

Пройти приемочные испытания! Показать себя хорошо на реальных входных данных. Будут ли среди них такие плохие данные, ради которых стоит перестраховываться и увеличивать перебор? (по сути, можно считать, мы исследуем переход к вероятностным алгоритмам или «эффективности для почти всех исходных данных»).

Возможно конечно когда-нибудь в этой задаче дополнят тест-сет, и это решение не пройдет… так что оставим как челлендж на «отл» (при условии, что есть «одна теоретическая задача») →

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

Челледж на «хор» → подобрать входные данные, на которых вот это решение даст неправильный результат.


  1. Не надо так весело разбрасываясь памятью оптимизировать в продакшне реальных проектов, если действительно этот размен не будет оправдан!