Blog:Advanced Algorithms/Python-оптимизация жадного алгоритма из codechef - История изменений

StasFomin в 09:39, 5 мая 2022

2022-05-05T09:39:51Z

StasFomin в 00:06, 5 мая 2022

2022-05-05T00:06:33Z

StasFomin в 00:04, 5 мая 2022

2022-05-05T00:04:43Z

StasFomin в 00:01, 5 мая 2022

2022-05-05T00:01:57Z

StasFomin в 23:22, 4 мая 2022

2022-05-04T23:22:06Z

StasFomin в 23:09, 4 мая 2022

2022-05-04T23:09:21Z

StasFomin в 21:55, 4 мая 2022

2022-05-04T21:55:19Z

StasFomin в 21:54, 4 мая 2022

2022-05-04T21:54:47Z

StasFomin в 21:49, 4 мая 2022

2022-05-04T21:49:46Z

StasFomin в 21:38, 4 мая 2022

2022-05-04T21:38:36Z

Внесённые изменения

@@ Строка 15: / Строка 15: @@
 Вот, нарисовал картинку в терминах исходной версии программы:
-[[File:chefstr2.svg|800px|center]]
+[[File:Python-оптимизация жадного алгоритма из codechef_2022-05-05_12-39-25_image0.png|center|800px]]
 Мы можем попробовать делать циклы из подстрок разной длины («ind»), повторяющиеся разное число раз «ks», чтобы получилась строка, нужной длины или чуть длиннее (не больше чем на «ind»).

@@ Строка 150: / Строка 150: @@
 ** ну либо обосновать, что действительно, можно опустить верхнюю оценку максимальной длины цикла в переборе.
 Челледж на «хор» → подобрать входные данные, на которых [https://www.codechef.com/viewsolution/64250125 вот это решение даст неправильный результат].
 {{wl-publish: 2022-05-05 00:01:56 +0000 | StasFomin }}

@@ Строка 150: / Строка 150: @@
 ** ну либо обосновать, что действительно, можно опустить верхнюю оценку максимальной длины цикла в переборе.
 Челледж на «хор» → подобрать входные данные, на которых [https://www.codechef.com/viewsolution/64250125 вот это решение даст неправильный результат].
 {{wl-publish: 2022-05-05 00:01:56 +0000 | StasFomin }}

@@ Строка 134: / Строка 134: @@
 Пора подумать внимательно, зачем нам так много нужно вложенных циклов.
 * Внешний цикл по длинам подстрок — ладно, пусть остается.
-* А два внутренних — по сути, подсчет «частот символов на разноцветных путях», и расчет из этого количества операций. Давайте заменим это на один цикл, по самой строке (вернее по массиву индексов символов), и для каждого индекса, будем решать, частоту какого символа (из «lenalf» символов) и на каком «пути» (из «ind» возможных путей) он увеличивает. {{diff| 20571 | Заводим списки векторы frequency — по сути, двухмерный массив, который моделируем одномерным списком, и массив max_frequency}} → {{@|9.1}} удивительно! Выигрыш есть, но совсем небольшой.
+* А два внутренних — по сути, подсчет «частот символов на разноцветных путях», и расчет из этого количества операций. Давайте заменим это на один цикл, по самой строке (вернее по массиву индексов символов), и для каждого индекса, будем решать, частоту какого символа (из «lenalf» символов) и на каком «пути» (из «ind» возможных путей) он увеличивает. {{diff| 20571 | Заводим списки векторы frequency — по сути, двухмерный массив, который моделируем одномерным списком, и массив max_frequency}} → {{!|9.1}} удивительно! Выигрыш есть, но совсем небольшой. А ведь еще мы память тратим, но вроде тут она бесплатна<ref>Не надо так весело разбрасываясь памятью оптимизировать в продакшне реальных проектов, если действительно этот размен не будет оправдан!</ref>.
-----
+Пройти приемочные испытания! Показать себя хорошо на реальных входных данных.
-{{wl-publish: 2022-05-01 02:48:25 +0000 | StasFomin }}
+Будут ли среди них такие плохие данные, ради которых стоит перестраховываться и увеличивать перебор? (по сути, можно считать, мы исследуем переход к вероятностным алгоритмам или «эффективности для почти всех исходных данных»).

@@ Строка 134: / Строка 134: @@
 Пора подумать внимательно, зачем нам так много нужно вложенных циклов.
 * Внешний цикл по длинам подстрок — ладно, пусть остается.
-* А два внутренних — по сути, подсчет «частот символов на разноцветных путях», и расчет из этого количества операций. Давайте заменим это на один цикл, по самой строке (вернее по массиву индексов символов), и для каждого индекса, будем решать, частоту какого символа (из «lenalf» символов) и на каком «пути» (из «ind» возможных путей) он увеличивает.
+* А два внутренних — по сути, подсчет «частот символов на разноцветных путях», и расчет из этого количества операций. Давайте заменим это на один цикл, по самой строке (вернее по массиву индексов символов), и для каждого индекса, будем решать, частоту какого символа (из «lenalf» символов) и на каком «пути» (из «ind» возможных путей) он увеличивает. {{diff| 20571 | Заводим списки векторы frequency — по сути, двухмерный массив, который моделируем одномерным списком, и массив max_frequency}} → {{@|9.1}} удивительно! Выигрыш есть, но совсем небольшой.
-−

@@ Строка 5: / Строка 5: @@
 {{oldid|1=chefstr2.py|2=20542|3=Первая версия}}
-Видимо легкий перебор, два-три вложенных цикла (три цикла, что-то дофига, причем два тут явно с зависимостью от длины входа — не к добру), что-то считается, что-то отбирается по максимуму…,  суммируется, отбирается по минимуму — типичный жадный алгоритм.
+Видимо легкий перебор, три вложенных цикла (три цикла, что-то дофига, причем явно с зависимостью от длины входа — не к добру), что-то считается, что-то отбирается по максимуму…,  суммируется, отбирается по минимуму — типичный жадный алгоритм.
 Cмотрим описание задачи [[Codechef/CHEFSTR2]], даже сразу  переходим по ссылке [https://discuss.codechef.com/t/chefstr2-editorial/83721 на разбор и разъяснение].
@@ Строка 128: / Строка 128: @@
 * Попытка {{diff| 20564 | поставить более вероятную ветку в первый «if» не помогла }} → {{@|13.1}}.

@@ Строка 123: / Строка 123: @@
    frequency[symbols[(input_str[j])]]
-Давайте {{diff| 20559 | сразу переведем строку в байт-массив индексов символов, и будем работать с ним }} → {{!|13.7}} — почти в два раза!
+* Давайте {{diff| 20559 | сразу переведем строку в байт-массив индексов символов, и будем работать с ним }} → {{!|13.7}} — почти в два раза!
-Давайте {{diff| 20562 | не уныло обнулять вектор частот, а сразу выделять новый забитый нулями }} → {{!|13.1}}.
+* Давайте {{diff| 20562 | не уныло обнулять вектор частот, а сразу выделять новый забитый нулями }} → {{!|13.1}}.
-{{diff| 20564 | попытка поставить более вероятную ветку в первый «if» не помогла }} → {{@|13.1}}.
+* Попытка {{diff| 20564 | поставить более вероятную ветку в первый «if» не помогла }} → {{@|13.1}}.