Скорость вычислений на Python (урок №4)
ฝัง
- เผยแพร่เมื่อ 28 ก.พ. 2021
- Курс из 15 занятий, читается весной 2021 года в МФТИ, школа ЛФИ, 2 курс.
Тема 4-го занятия: Скорость вычислений и способы её увеличить.
Материалы курса: github.com/tkhirianov/pydatan
Telegram-канал для общения вольнослушателей: t.me/tkhirianov_data_analysis...
Спонсировать канал: / tkhirianov или www.paypal.me/tkhirianov
Вместо спонсорства мне предлагаю помочь Тимофею 7 лет из Набережных Челнов восстановить ухо: bolshie-dela.com/podarite-voz...
![ตีสิบเดย์ [FULL] | ครอบครัวสะท้านทุ่ง "นางบี & อ้ายสติ๊ก"](http://i.ytimg.com/vi/A1rhYcxxNtA/mqdefault.jpg)
Важные замечания и исправления:
1:13:21 -- запуск через Pool получился настолько быстрее только потому, что я забыл в range вписать +1, то есть не вычислялось последнее число Фибоначчи.
1:37:48 -- долго не мог победить undefined symbol, а затем вычитал в nesi.github.io/perf-training/python-scatter/ctypes что нужно делать extern "C" в файле.cpp
В репозиторий выложил исправленный файл статистики с новым замененным временем работы с Pool, а также Makefile для сборки С++ библиотечки с функцией fib.
Мне кажется, что если убрать ограничение по времени от урока, то Тимофей Хирьянов расскажет нам все про програмированию. На каждом уроке узнаю кучу нового материала. Спасибо Вам большое.
Век живи, век учись! Буду заниматься! Спасибо за мотивацию!
Сам с удовольствием смотрю (чтобы не отупеть), привлёк к просмотру своих работников и готов спонсировать продвижение Вашего канала. Тимофею, 7 лет из Набережных Челнов в ближайшее время деньги переведем. Спасибо за интересное занятие.
Вот! На могилах сразу понятно стало)
Спасибо за лекцию!
Лайк за обучение. Спасибо Тимофей)
Отличная подача материала! Спасибо!
Надеюсь на продолжение курса, как всегда очень интересно
У Вас замечательный подход к Преподаванию предмета, даже мне учившемуся в 2003г ( Assembler, Pascal, C++) хочется с Вашими лекциями изучать Python, хотя это для меня дело факультативное. В работе моей увы все больше железо, а не программное обеспечение. Но тянет к старому... Успеха Вам!
Тайм-коды: мультипроцессность/ multiprocessing, родительский процесс, дочерний процесс, очередь/queue
0:00 скорость вычислений. Какая бывает параллельность. Иногда необходима асинхронность
3:38 времени вычисления зависит от компьютера, на котором производятся вычисления
5:51 Код. Пример№1 1_fib_simple. py самый простой, без параллельности. import time
9:15 Запуск Пример№1: один процесс на Python - 58,11 сек
9:58 нити могут помочь ускорить на другом языке, из-за GIL нет реальной возможности ускорения кода на чистом Питоне
10:38 Мультипроцессность multiprocessing . Process процесс. Многопоточность
12:31 Код. Пример№2 2_process. py. Распараллеливание, без очередей from multiprocessing import Process
13:53 схема вычислительных процессов: родительский процесс, дочерние процессы. Множественная параллельность на Python регулируется не интерпретатором, а ОС. Без общей памяти shared memory
20:23 механизмы передачи данных и возврата. через модуль multiprocessing просто передать параметры функции. Без очередей
21:15 Код. Пример№2
32:16 запущенные процессы
35:29 Запуск Пример№2: 40 процессов - по одному на каждое число - 36,67 сек
37:31 №2 блок-схема
38:50 Пример№3. блок-схема. Модифицирование передачи информации: не по 1 воркеру(исполнитель, вычислительный процесс) на 1 процесс, а цикл с процессами на всего несколько воркеров. Очередь Queue
46:38 Код. Пример№3 3_queues. py
48:29 Queue Очередь из multiprocessing
49:22 Организация параллельной работы. put и get в/из очереди
54:52 Родительский процесс/Parent process и Дочерний процесс/Child. Воркеры/ Workers
59:12 Запуск Пример№3
1:03:28 очереди атомарны
1:05:57 Запуск Пример№3 с очередями, 4 процесса: 34,94 сек
1:07:16 Запуск Пример№3 с очередями, 2 процесса: 37,40 сек
1:09:06 Pool в multiprocessing, вместо process с queue. Нет очередей, нет явного создания вычислительных процессов, сортировать не надо
1:10:30 Код. Пример№4 4_pool. py
1:14:12 Запуск Пример№4 Пул из 4 процессов: 27,26 сек
1:15:00 Код. Пример№5 5_fib_numbers. cpp код на С++ без параллельности
1:17:52 Запуск Пример№5 на С++: 1,26 сек
1:18:55 параллельность в С++
1:20:14 Пример№6 библиотека ctypes. Способ вычисления на Си, но запускаться из родительского Питона 6_fib.cpp
1:21:43 код на С++ скомпилировать, как shared memory
1:24:58 ctypes запуск в Питоне кода, который написан на С
1:30:27 Код. Пример№6 6_fib. o
1:38:36 2 главных вопроса, когда хотим что-то ускорить: 1) язык программирования, 2) более важно: выбор правильного алгоритма
1:39:43 Код. Пример№7 kiss. py динамическим программированием на Питоне
1:42:20 Запуск Пример№7: правильным алгоритмом 0,02 сек
1:44:08 Вывод. С чего начинать ускорение и что дальше
Ещё одно красивое решение без параллельности через автоматическую мемоизацию:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n: int) -> int:
if n < 2:
return 2
return fib(n - 2) + fib(n - 1)
if __name__ == "__main__":
for i in range(1000):
print(f"fib({i})={fib(i)}")
Финалочка красивая))
Большое спасибо! 👍
Из интересу поэкспериментировал, сколько чисел Фибоначчи динамическим программированием будет подсчитано за сравнимое с рекурсией 40 чисел время - около 35 сек. На сравнимом компе (i5 двухъядерный 2012 года) получилось 140000 (Cто сорок тысяч!) Посчиталось за 35.14 секунд. Заодно выяснил, что стосорокатысячное число Фибоначчи состоит из 29583 десятичных цифр. Полезное знание :)
Спасибо
Когда следующая серия? Неделя прошла уже. каникулы что ли?
Тимофей Федорович, убедительная просьба: сделайте, пожалуйста, возможность спонсировать Ваш канал.
К сожалению, это невозможно без монетизации, а я не буду этого делать, поскольку реклама -- зло.
И ещё раз напоминаю, что Тимофей 7 лет из Набережных Челнов очень нуждается в нашей помощи:
bolshie-dela.com/podarite-vozmozhnost-slyshat-timofey-smirnov-7-let-g-naberezhnye-chelny
Там же есть Patreon, через него можно спонсировать.
Некоторые просто пишут номер кредитной карты.
Воистину, ничто так не вредит свободе распространения знаний, как примотанная скотчем монетизация. Нынче, при наличии огромного количества "монетарных" IT-инфокурсов, на поверку являющихся не более чем выколачиванием денег из неофитов, Тимофей несомненно выдающийся преподаватель, в лучших традициях и стандартах высшей школы. Здоровья и сил Тимофею, в его благородном деле!
Очень бы хотелось увидеть видео по применению параллельных вычислений для обеспечения интерактивности, например как обходить блокирующую функцию input?... И еще про совместный доступ к памяти из разных процессов тоже! Спасибо! :)
Это можно. Через некоторое время.
По своему опыту могу сказать, что в реальной работе программисту стоит по возможности привлекать специалистов из предметной области - потому что да, мы заменили рекурсию на цикл (по сути хитрый синтаксис питона в последнем варианте об этом, но я работаю с Java) и потратили ресурсы (свое время, которое заказчику стоит денег), но математик или специалист по алгоритмам мог бы указать на вариант расчета через матрицы, когда за одну итерацию мы получаем более одного числа Фибоначчи. Интересующимся (можно назвать это задачей со звёздочкой) - подробности здесь: ru.wikibooks.org/wiki/Вычисление_чисел_Фибоначчи (в конце).
Но в рамках урока, который безусловно прекрасен - это излишне. Да и бизнесу зачастую важна скорость разработки и результат, оптимизация это уже когда-нибудь потом, как правило.
Тимофей Федорович, спасибо за урок - были бы такие 5 лет назад, когда только начинал - может был бы питонистом)
Спасибо за развёрнутое замечание.
Надеюсь, мой предыдущий комментарий и pr в ваш репо вам так или иначе помогли)
Некоторые дополнения я всё же напишу:
1. Честная (ну почти) многопроцессность в Python есть, реализована она так: для каждого процесса просто запускается свой интерпретатор.
2. Количество процессов как для воркеров в application server (будь то gunicorn или uwsgi), так и внутри программ принято считать как 2 * cpu_count + 1. Кол-во ядер можно узнать через os.cpu_count().
3. top - старая утилита, вместо неё сейчас используют htop, которая позволяет искать процессы, фильтровать, убивать их, смотреть используемые процессом переменные окружения и файлы etc.
4. Также рекомендую познакомиться с tmux, который позволяет разбить окно терминала на несколько не зависящих друг от друга частей. Это поможет вам писать код в одном блоке одного окна терминала, запускать код в другом блоке.
5. Глобальные константы принято писать в UPPERCASE для удобства чтения кода: если встретилась какая-то штука в верхнем регистре, то это, очевидно, некоторая константа.
6. Начиная с Python3.8, вместо f"number = {number}" можно писать f"{number = }", или f"{f(x) = }". Некоторые тонкости форматирования строк: realpython.com/python-f-strings/
7. В конце вы написали алгоритм подсчёта чисел Фибоначчи, но сделали это неэффективно по памяти: каждое из чисел будет сохраняться, т.е. алгоритм O(n). А если понадобиться посчитать 100-е или 1000-е число, то RAM может попросту закончиться (например, 2**1_000_000 будет весить 133'360 (!) байт).
Я думаю, датасатанистов можно познакомить с генераторами, ведь эта штука несложная: pastebin.com/btcUAVka (реализация почти того же алгоритма только с О(1) по памяти)
8. Для серьёзного ускорения Python кода используется Cython - библиотека, позволяющая писать из питона на С. Вновь отсылаю к курсу «Async Techniques and Examples in Python» Майкла Кеннеди. Весь курс занимает 5 часов, там есть блок по Cython. Я думаю, ознакомление с ним займёт пару часов). Он есть на nnmclub с субтитрами, но если что курс я могу вам скинуть.
9. Type hints - это обязательный аспект кода в продакшене. Заставляйте, пожалуйста, студентов писать подсказки типов.
Ну и соблюдать PEP 8, PEP 257 и т.д.)
Спасибо за подробный комментарий. 7. С генераторами я знакомил учащихся на 2-м уроке этого курса, просто сейчас не стояло такой задачи.
1. Через какой модуль? Ведь в multiprocessing именно так?
4. У меня стоит терминал terminator, который и так это позволяет, только я почему-то не пользуюсь. Дело привычки.
2, 3, 5, 6, 9 -- учту. Курс 8 постараюсь посмотреть как только найдётся время для задач низкого приоритета, спасибо ещё раз за ссылку.
@@tkhirianov всегда пожалуйста)
1. Да, это стандартная многопроцессность
@@tkhirianov если не секрет, подскажите, а вы и так это всё знали: про воркеры, очереди и всё остальное или всё же мой предыдущий комментарий внёс некоторую лепту?
@@user-zg2bx5cb3d Конечно привнесли, что вы. Спасибо за ваш труд! Я стараюсь внимательно относиться к замечениям и, конечно, учусь у своих зрителей.
@@tkhirianov это прекрасно, что вы готовы обучаться и изучаете что-то новое!
К этому способны далеко не многие, побольше бы таких как вы
Если запихивать задания в очередь начиная с наиболее сложных, можно выиграть время. В данном случае это аж несколько секунд! У меня получилось 27 против 32 в прямом порядке на четырёх ядрах Core i5 чего-то там
Тимофей Федорович, можно ли будет начать смотреть этот курс после просмотра вашего курса "2020 Практика программирования на Python 3"? Или нужно что-то ещё до этого пройти, чтобы понимать о чем говорится?
TL;DR: Как увеличить скорость выполнения программы на Питоне? Переписать на Плюсах. )
1:17:18
@@tkhirianov да-да, я именно поэтому и пошутил )
Кстати, Cython даёт очень хорошие результаты при минимальном изменении питонячьего кода. А ещё он позволяет отключить GIL и считать, задействуя все ядра процессора одновременно, что, опять же, самым положительным образом сказывается на быстродействии.
Когда я заставлял распберри дёргать ногой сначала через питон, потом через си++, то у плюсов по сравнению с питоном выигрыш в быстродействии был в 26 раз! Т.е. переключение ноги из 0 в 1 и обратно в цикле на питоне дало на выходе частоту в 1.0-1.3 МГц, а на плюсах -- 26-27 МГц.
Спасибо за лекцию, Тимофей. Вас очень часто смущал результат fib(0)=1 . Просто напишите это - и проблема исчезнет: if n > 2 else n
Для рекуррентного алгоритма изменится время вычислений, т.к. увеличится глубина дерева вызовов (а это дерево Фибоначчи). Это нужно было бы переписывать во всех файлах.
@@tkhirianov Вы меня не поняли - я может быть неточно выразился. У Вас во всех файлах функция выглядит так:
def fib(n: int) -> int:
return fib(n-1) + fib(n-2) if n > 2 else 1
Нужно всего лишь поменять последнюю единичку после else на переменную n :
return fib(n-1) + fib(n-2) if n > 2 else n
Тогда вычисляться будет правильно: fib(1) = 1, а fib(0) = 0. На глубину деревьев это никак не повлияет.
@@VadimKochkarev Тогда для n=2 будет fib(2) == 2, что неверно. Поменять 1 на n с сохранением значений можно только вместе с if n >= 2 else n, а это и приведёт к увеличению глубины дерева вызовов.
@@tkhirianov Большое спасибо за пояснение - это я торможу, не обращаю внимание на Вашу двойку. В каноническом виде алгоритм выглядит:
return fib(n-1) + fib(n-2) if n > 1 else n.
Да, это приводит к увеличению количества рекурсий и времени выполнения примерно в 1.6 раза. Но зато это методологически правильнее :) Потому как оба решения не блещут оптимальностью и интересны только в образовательных целях.
Тимофей Федорович, спасибо за лекцию. Не могли бы Вы прокомментировать использование библиотеки numba для ускорения и распараллеливания кода. Заранее спасибо.
Спасибо за отсылку. В следующий раз, вероятно.
Я сделал пример 8 в репозитории и замерил время: github.com/tkhirianov/pydatan/blob/main/lesson_4/8_numba_used.py
@@tkhirianov Спасибо большое. У меня получились схожие результаты: примерно в 2 раза медленнее "чистого" Си, но быстрее "стандартного" Питона ~20-25 раз. Какое Ваше мнение, стоит ли использовать numba, или все таки лучше внедрять shared функции из Си?
@@alexeyshulgin4556 Очевидно, стоит внедрять, если это ничего не стоит. Но это лишь "мнение", поскольку я ничего не знаю о побочных эффектах -- есть ли они при использовании Numba или нет.
@@tkhirianov Спасибо большое за Ваше мнение! Скажите пожалуйста, а Вы выложите остальные лекции курса? Очень хотелось бы прослушать его до конца.
👏👍
Спасибо за лекцию. В варианте с pool резлуьтат вывода на экран отличался от остальных, не вышло последнее число фибоначчи. Поэтому результат 27 секунд не верен.
Согласен. Упустил +1 при загрузке заданий.
А как правильнее запускать параллельность, но если время создание очереди в родительском процессе тоже имеет значение? Плюс очередь перед запуском процессов содержит некие данные, а это значит она занимает память, которая тоже не резиновая. Как бы так не получилось что не хватит памяти в процессе набивания очереди данными.
Простейший пример - импорт чего то из одной базы данных в другую. Запрос на импорт вернул миллион строк. Начинаешь формировать порции данных пакетами по N строк, и воркер/процесс должен выполнять некоторое сложное преобразование данных и записывать скажем в несколько разных таблиц.
То есть данные должны начать обрабатываться в дочерних процессах ещё до того как будет закончен обход выборки результата запроса.
И самый интересный вопрос. Если по какой-то причине один из дочерних процессов кильнет какой-то негодяй, не хочется повторять весь процесс сначала, а хочется повторить исключительно обработку только тех данных, которые умрут вместе с убитым дочерним процессом.
Вычисление функции Фибоначчи конечно прикольно для урока, что её можно алгоритмически ускорить, но жизнь имеет другие краски 😀
Очень странно: код на 32:00 минуте запускаю в IDLE - не выводятся строки "worker ..., PID ..."
Запускаю в PyCharm тот же код - выводятся. Кто-нибудь знает в чем дело?
f"string" появились в python3.6 и работают во всех более новых версиях. Соотв, PyCharm у вас загружает версию, которая умеет работать с f-строками, а IDLE загружает старую версию ядра python (до 3.6), поэтому работать с этими строками не умеет. Попробуйте print("worker: {}, pid: {}".format(worker, os.getpid())) Работать будет во всех интерпретаторах python3*
Здравствуйте. Нравятся Ваши лекции, но записей стало очень много и это затрудняет поиск интересующих тем. Может есть возможность добавить вступительный кадр на заставку видео (с темой видео)?
Простите, мне проще писать тему текстом в заголовке, а не в заставке.
На канале же всё по плейлистам разложено удобно.
У вас ошибка при работе с пулом, в range, нужно заменить final_fibonacci_number на final_fibonacci_number+1. пул не просчитал самый сложный, 40ой элемент
Запуск Си из Питона
from ctypes import cdll
lib = cdll.LoadLibrary("./libfoo.so")
lib.Foo_bar("hello")
th-cam.com/video/UA4Wsp3AWYc/w-d-xo.html
Эффект взорвавшийся бомбы в голове, но что бы это почувствовать, надо смотреть с самого начала
ПОМОГИТЕ ПОЖАЛУЙСТА С КОДОМ!!! В Pydroid 3 код работает но только в этой программе. В других ошибка: Traceback (most recent call last):
File "", line 1, in
ModuleNotFoundError: No module named 'pyowm'
Код:from pyowm.owm import OWM
from pyowm.utils.config import get_default_config
config_dict = get_default_config()
config_dict['language'] = 'ru'
owm=OWM('a5aeac62b5011815ca655f34d5145865', config_dict)
while True:
try:
place = input('У якому місті ви хочете знати погоду? Введіть правильну назву міста: ')
monitoring = owm.weather_manager().weather_at_place(place)
weather = monitoring.weather
status = weather.detailed_status
temp = weather.temperature('celsius')["temp"]
print(f'В місті {place} зараз {status}, а температура сягає {temp} градусів')
break
except:
pass
if temp < 10:
print("Зараз дуже холодно, одягайся тепло")
elif temp < 20:
print("Зараз трохи холодно, одягайся тепліше")
else:
print("Зараз тепло, зручно й легко одягайся")
from pyowm.owm import OWM
from pyowm.utils.config import get_default_config
config_dict = get_default_config()
config_dict['language'] = 'ru'
owm=OWM('a5aeac62b5011815ca655f34d5145865', config_dict)
while True:
try:
place = input('У якому місті ви хочете знати погоду? Введіть правильну назву міста: ')
monitoring = owm.weather_manager().weather_at_place(place)
weather = monitoring.weather
status = weather.detailed_status
temp = weather.temperature('celsius')["temp"]
print(f'В місті {place} зараз {status}, а температура сягає {temp} градусів')
break
except:
pass
if temp < 10:
print("Зараз дуже холодно, одягайся тепло")
elif temp < 20:
print("Зараз трохи холодно, одягайся тепліше")
else:
print("Зараз тепло, зручно й легко одягайся")
Жаль, что робовойс на этой записи :(
Жаль. Надеюсь, однажды смогу решить эту проблему.
@@tkhirianov проблема со звуком в том, что он идёт через какую-то видеоконференцию (zoom, jitsi..), а она его портит, там алгоритмы подавления эха стоят (слышу как работают). лучше звук захватывать напрямую с микурофона.
Такое впечатление, что Тимофей просто прочитал сам материал за день до самого урока. И даже примеры приводит на Jupiter.
Красота: 99% времени лекции отправили в помойку. Алгоритм решил все проблемы. Может, на неудачные варианты отводить меньше времени?
Увы, Вы вообще не оценили методическую задумку... Я не в production сижу, а урок провожу, а вычисление чисел Фибоначчи для меня не насущная жизненная задача, а УЧЕБНАЯ, взятая именно потому, что это -- ресурсоёмкое вычисление, у которого ЕСТЬ быстрая версия (через динамическое программирование). Но НЕ ВСЕГДА существует простой алгоритм. Потому и бывает нужно использовать параллельное программирование, потому я и объясняю основы его использования в Python.