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

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

Продолжим тему 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. Не надо так весело разбрасываясь памятью оптимизировать в продакшне реальных проектов, если действительно этот размен не будет оправдан!

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

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

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