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

StasFomin в 10:18, 4 мая 2022

2022-05-04T10:18:19Z

StasFomin в 10:17, 4 мая 2022

2022-05-04T10:17:24Z

StasFomin в 10:03, 4 мая 2022

2022-05-04T10:03:05Z

StasFomin в 02:49, 1 мая 2022

2022-05-01T02:49:14Z

StasFomin в 02:48, 1 мая 2022

2022-05-01T02:48:25Z

StasFomin в 02:48, 1 мая 2022

2022-05-01T02:48:16Z

StasFomin в 02:35, 1 мая 2022

2022-05-01T02:35:20Z

StasFomin в 01:45, 1 мая 2022

2022-05-01T01:45:26Z

StasFomin в 01:24, 1 мая 2022

2022-05-01T01:24:49Z

StasFomin в 01:21, 1 мая 2022

2022-05-01T01:21:39Z

@@ Строка 215: / Строка 215: @@
 Да, тут многое можно было написать красивей<ref>жалко, что пришлось вставлять лишний парсинг входа, с точки зрения чистых алгоритмов это конечно хак, хотя в любом случае это читаемый код, а не С++шный «лишбыработало» [https://www.codechef.com/viewsolution/14955997], [https://www.codechef.com/viewsolution/15415158])</ref>, очень желательны комментарии для будущих читателей кода… но для целей иллюстрации, как оптимизировать питоновский код, думаю, достаточно, чтобы не перегружать статью!
-Удивительно, что один из студентов решил [https://www.codechef.com/viewsolution/64117884 эту задачу на на CPython], хотя это конечно хак, запускать питоном чистый ассемблер!
+Удивительно, что один из наших студентов решил [https://www.codechef.com/viewsolution/64117884 эту задачу на на CPython], хотя это конечно хак, запускать питоном чистый ассемблер!
 Не надо так делать в наших задачах, лучше подумать над алгоритмом, но всеже тема интересная и попробуем написать про такой подход статью-заметку.

@@ Строка 213: / Строка 213: @@
 [[File:Python-оптимизация алгоритма динамического программирования из codechef_2022-05-01_05-40-36_image0.png|center|640px]]
-Да, тут многое можно было написать красивей<ref>жалко, что пришлось вставлять лишний парсинг входа, с точки зрения чистых алгоритмов это конечно хак.</ref>, а не С++шный «лишбыработало» [https://www.codechef.com/viewsolution/14955997], [https://www.codechef.com/viewsolution/15415158])
+Да, тут многое можно было написать красивей<ref>жалко, что пришлось вставлять лишний парсинг входа, с точки зрения чистых алгоритмов это конечно хак, хотя в любом случае это читаемый код, а не С++шный «лишбыработало» [https://www.codechef.com/viewsolution/14955997], [https://www.codechef.com/viewsolution/15415158])</ref>, очень желательны комментарии для будущих читателей кода… но для целей иллюстрации, как оптимизировать питоновский код, думаю, достаточно, чтобы не перегружать статью!
 </ref>, очень желательны комментарии для будущих читателей кода… но для целей иллюстрации, как оптимизировать питоновский код, думаю, достаточно, чтобы не перегружать статью!
-Удивительно, что один из студентов решил <a href="https://www.codechef.com/viewsolution/64117884">эту задачу на на CPython</a>, хотя это конечно хак, запускать питоном чистый ассемблер!
+Удивительно, что один из студентов решил [https://www.codechef.com/viewsolution/64117884 эту задачу на на CPython], хотя это конечно хак, запускать питоном чистый ассемблер!
 Не надо так делать в наших задачах, лучше подумать над алгоритмом, но всеже тема интересная и попробуем написать про такой подход статью-заметку.

@@ Строка 213: / Строка 213: @@
 [[File:Python-оптимизация алгоритма динамического программирования из codechef_2022-05-01_05-40-36_image0.png|center|640px]]
-Да, тут многое можно было написать красивей, очень желательны комментарии для будущих читателей кода… но для целей иллюстрации, как оптимизировать питоновский код, думаю, достаточно, чтобы не перегружать статью!
+Да, тут многое можно было написать красивей<ref>жалко, что пришлось вставлять лишний парсинг входа, с точки зрения чистых алгоритмов это конечно хак.</ref>, а не С++шный «лишбыработало» [https://www.codechef.com/viewsolution/14955997], [https://www.codechef.com/viewsolution/15415158])
 ----
 {{wl-publish: 2022-05-01 02:48:25 +0000 | StasFomin }}

← Предыдущая		Версия 02:49, 1 мая 2022
Строка 218:		Строка 218:

	Он нам не очень нужен (есть читаемое решение на питоне<ref>Хотя конечно, нам жалко, что пришлось вставлять лишний парсинг входа, с точки зрения чистых алгоритмов это конечно хак.</ref>, а не С++шный «лишбыработало» [https://www.codechef.com/viewsolution/14955997], [https://www.codechef.com/viewsolution/15415158]), но, если интересно, то наверно можно предложить «отл» за курс, если получится пройти и с CPython 3.6		Он нам не очень нужен (есть читаемое решение на питоне<ref>Хотя конечно, нам жалко, что пришлось вставлять лишний парсинг входа, с точки зрения чистых алгоритмов это конечно хак.</ref>, а не С++шный «лишбыработало» [https://www.codechef.com/viewsolution/14955997], [https://www.codechef.com/viewsolution/15415158]), но, если интересно, то наверно можно предложить «отл» за курс, если получится пройти и с CPython 3.6
		+
		+	----
	{{wl-publish: 2022-05-01 02:48:25 +0000 \| StasFomin }}		{{wl-publish: 2022-05-01 02:48:25 +0000 \| StasFomin }}

← Предыдущая		Версия 02:48, 1 мая 2022
Строка 218:		Строка 218:

	Он нам не очень нужен (есть читаемое решение на питоне<ref>Хотя конечно, нам жалко, что пришлось вставлять лишний парсинг входа, с точки зрения чистых алгоритмов это конечно хак.</ref>, а не С++шный «лишбыработало» [https://www.codechef.com/viewsolution/14955997], [https://www.codechef.com/viewsolution/15415158]), но, если интересно, то наверно можно предложить «отл» за курс, если получится пройти и с CPython 3.6		Он нам не очень нужен (есть читаемое решение на питоне<ref>Хотя конечно, нам жалко, что пришлось вставлять лишний парсинг входа, с точки зрения чистых алгоритмов это конечно хак.</ref>, а не С++шный «лишбыработало» [https://www.codechef.com/viewsolution/14955997], [https://www.codechef.com/viewsolution/15415158]), но, если интересно, то наверно можно предложить «отл» за курс, если получится пройти и с CPython 3.6
		+	{{wl-publish: 2022-05-01 02:48:25 +0000 \| StasFomin }}

← Предыдущая		Версия 02:48, 1 мая 2022
Строка 205:		Строка 205:
	Pypy time → 2.099s		Pypy time → 2.099s
	Вызовов calculate → 3477870		Вызовов calculate → 3477870
		+
		+	Явно улучшилось!
		+
		+	Да, тут многое чешеться еще улучшить, но пора попробовать, вдруг уже пройдет →
		+	[https://www.codechef.com/viewsolution/63961917 ура, проходит]!
		+
		+	[[File:Python-оптимизация алгоритма динамического программирования из codechef_2022-05-01_05-40-36_image0.png\|center\|640px]]
		+
		+	Да, тут многое можно было написать красивей, очень желательны комментарии для будущих читателей кода… но для целей иллюстрации, как оптимизировать питоновский код, думаю, достаточно, чтобы не перегружать статью!
		+
		+	Возможно тут даже остался челледж → оптимизировать так, чтобы проходил CPython.
		+
		+	Он нам не очень нужен (есть читаемое решение на питоне<ref>Хотя конечно, нам жалко, что пришлось вставлять лишний парсинг входа, с точки зрения чистых алгоритмов это конечно хак.</ref>, а не С++шный «лишбыработало» [https://www.codechef.com/viewsolution/14955997], [https://www.codechef.com/viewsolution/15415158]), но, если интересно, то наверно можно предложить «отл» за курс, если получится пройти и с CPython 3.6

← Предыдущая		Версия 02:35, 1 мая 2022
Строка 140:		Строка 140:

	(ничего интересного не достигли)		(ничего интересного не достигли)
		+
		+
		+	Введем глобальную переменную 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»
		+	<blockquote>
		+	… делаем {{diff\|20506\|правку}}, получаем {{oldid\|1=digprime.py\|2=20506\|3=версию}}, для которой …
		+	</blockquote>
		+	радикально уменьшились рекурсивные вызовы (хотя внутри функции теперь больше работы), но время тоже падает
		+
		+	CPython time → 17.762s
		+	Pypy time → 2.099s
		+	Вызовов calculate → 3477870

@@ Строка 124: / Строка 124: @@
 Что видно — огромное количество (43.5M) рекурсивных вызовов функции «calculate», ну и еще там где-то зря дергаются лишний раз «len()».
-Начинаем оптимизировать.
+Начинаем оптимизировать, учитываем [https://discuss.codechef.com/t/digprime-editorial/13433 пропущенную эвристику]<ref>что когда у нас «230» → то на второй цифре можно сразу вернуть число десятков, не перебирая глубже</ref>,
 делаем  {{diff|20497|правку}}, получаем {{oldid|1=digprime.py|2=20497|3=версию}}, для которой
@@ Строка 130: / Строка 130: @@
   Pypy time → 2.722s
   Вызовов calculate → 26874678

@@ Строка 100: / Строка 100: @@
   sys     0m0.351s
-−
   time pypy3 digprime.py < big-samples.txt > big-our-results.txt
@@ Строка 116: / Строка 116: @@
 <tab head=top border=1 sep="spaces" cellspacing=5 class="wikitable">
     ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     0.000    0.000  103.393  103.393 {built-in method builtins.exec}
     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}
+43546528    6.380    0.000    6.380    0.000 {built-in method builtins.len}
 </tab>