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

Материал из DISCOPAL
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

Chefstr2.svg

Мы можем попробовать делать циклы из подстрок разной длины («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» не обязательно перебирать до исходной длины строки, идея понятна, у меня кончились красивые цвета для путей.


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

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-код из разъяснения, компилируем.






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

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

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

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

Python-оптимизация алгоритма динамического программирования из codechef 2022-05-01 02-50-11 image0.png

и пишем примитивных генератор «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?

Python-оптимизация алгоритма динамического программирования из codechef 2022-05-01 02-58-12 image0.png

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

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

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

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

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

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


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

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

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

Python-оптимизация алгоритма динамического программирования из codechef 2022-05-01 03-36-58 image0.png

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

Увы, нет.

Python-оптимизация алгоритма динамического программирования из codechef 2022-05-01 03-34-48 image0.png

Обращаю внимание — 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
ncallstottimepercallcumtimepercallfilename:lineno(function)
10.0000.000103.393103.393{built-inmethodbuiltins.exec}
12.7162.716103.393103.393digprime.py:2(<module>)
43546528/10000093.6910.000100.0710.001digprime.py:19(calculate)
435465286.3800.0006.3800.000{built-inmethodbuiltins.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

Явно улучшилось!

Да, тут многое чешеться еще улучшить, но пора попробовать, вдруг уже пройдет → ура, проходит!

Python-оптимизация алгоритма динамического программирования из codechef 2022-05-01 05-40-36 image0.png

Да, тут многое можно было написать красивей[2], очень желательны комментарии для будущих читателей кода… но для целей иллюстрации, как оптимизировать питоновский код, думаю, достаточно, чтобы не перегружать статью!

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




  1. что когда у нас «230» → то на второй цифре можно сразу вернуть число десятков, не перебирая глубже
  2. жалко, что пришлось вставлять лишний парсинг входа, с точки зрения чистых алгоритмов это конечно хак, хотя в любом случае это читаемый код, а не С++шный «лишбыработало» [1], [2])

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.