Комментарии 13
Дельная статья, всё правильно объяснено.
Немножко недокрутили разве что степень параллелизма до окончательного вывода. А именно, при большом количестве ядер параллельная сортировка слиянием становится быстрее быстрой сортировки.
Было бы интересно расширить эксперемент.
Протестировать все количества массивов - от 1 до 17. Например, будет ли увеличение с 8 до 9 приводить к такому же росту времени, как с 7 до 8? Или увеличение времени окажется больше?
Ну и величину скачка времени при пересоде с 16 до 17 было интересно измерить.А также было бы интересно загрузить разным количеством массивов интеловский проц с его Р и Е ядрами.
Здесь несложно предсказать поведение: если количество задач, которые необходимо выполнить, больше, чем количество доступных логических ядер (16 < 17), то пул процессов будет управлять выполнением задач в очереди. Говоря простым языком, это как автомойка с 16 боксами и 17 машинами - 16 машин будут стоять в боксах, а одна ждать. Когда одна машина уедет с мойки, 17-ая машина заедет в её бокс. Когда 17-ую машину помоют и она уедет, функция asyncio.gather зафиксирует, что мы обслужили все машины
Гонять Кнута на питоне эт конечно сильный ход, я так навскидку даже не соображу, что именно вы в своей программе протестировали.
Кажется восхитительный микс из микроархитектуры процессора, реализации конкретного питона, вашей реализации алгоритмов (мм, вкусняшка left = [x for x in arr if x < pivot] ) и любопытного подбора параметров. А, и еще asyncio, но его деталей я к сожалению не знаю, поэтому сделаю очень смелое предположение, что никакого влияния он не оказал.
Привет, согласен с @molnij, микс очень странный. Напрягло еще в статье - упоминание asyncio. Вообще-то asyncio (а еще лучше curio) реализует кооперативную многозадачность (в статье ни слова). Причем это должны быть IO-bounded задачи, не вычисления.
<duschnila mode=on>
В питоне, как таковых корутин нет, есть генераторы. async def нужен питону для маркирования генератора как асинхронного и первичного запуска генератора, раньше маркировали декоратором @courutine. Маркировка async говорит о том, что в теле генератора может появиться await, кстати, await - это новая версия синтаксиса yield from для async генераторов.
</duschnila mode=off>
Но все равно, это знание никак не поможет статье, потому как асинхронное программирование в питоне, НЕ позволяет системе обрабатывать несколько задач одновременно. Всегда выполняется одна задача. В случае IO да, можно назвать выполнение "одновременным", но это происходит на отдельных контроллерах, в программе питона мы только проверяем флаги о завершении получения или передачи пакета данных.
Пропустим теоретическую часть, перейдем к практике. В Thread классе нет атрибута Thread.daemon есть Thread._daemonic (threading.py, ~905 строка). Потому у меня есть большие сомнения что все работает как планировалость. Я бы предложил такой вариант:
if __name__ == '__main__':
loop = asyncio.new_event_loop()
Thread(target=loop.run_forever, daemon=True).start()
ThreadedEventLoop не нужен. Но я продолжаю оставаться в неуверенности, что оно работает так, как задумано в статье.
algorithms.py вообще оставлю без комментариев, там жесть, конечно.
отличный комментарий. Спасибо, что сказали про Thread._daemonic - здесь моя невнимательность. Что касается применения модуля asyncio: использовал для реализации asyncio.gather чтобы дождаться завершения всех вызовов в списке call_coros
Хочу отбросить ваши сомнения - приложение работает так, как задумывалось и правильно. Я решил выполнить чистый код приложения, убрав графический интерфейс, многопоточность, асинхронку. Вместо этого будет синхронный код и чистый пул процессов с функцией map. Результаты идентичны, что и в приложении. Можете сами проверить
import random
from random import randint
import time
from concurrent.futures import ProcessPoolExecutor
random.seed(1)
def insert_sort(arr: int) -> None:
"""Insertion sort algorithm."""
N = len(arr)
for top in range(1, N):
k = top
while k > 0 and arr[k - 1] > arr[k]:
arr[k], arr[k - 1] = arr[k-1], arr[k]
k -= 1
def get_test_data(_numbers_amount, _arrays_number):
return [
[
randint(1, 1000) for n in range(_numbers_amount)
] for _ in range(_arrays_number)
]
if __name__ == "__main__":
start = time.time()
arr = get_test_data(30000, 5)
for a in arr:
insert_sort(a)
end = time.time()
print(end - start)
arr = get_test_data(30000, 5)
start = time.time()
with ProcessPoolExecutor() as process_pool:
process_pool.map(insert_sort, arr)
end = time.time()
print(end - start)
У меня результаты такие
183.37491822242737
37.8449387550354 - Выполнилось немного быстрее, т.к. турбо-буст у процессора отработал
arr = get_test_data(30000, 5)
start = time.time()
with ProcessPoolExecutor() as process_pool:
process_pool.map(insert_sort, arr)
Гонять огромные массы данных между процессами это скорее тестирование механики IPC в питоне (что в принципе тоже интересная тема). Может для чистоты эксперимента их стоит генерировать внутри дочернего процесса?
algorithms.py вообще оставлю без комментариев, там жесть, конечно
А по-моему это шедевр. Все алгоритмы сортировки, которые обычно спрашивают на собеседованиях, в одном файле. :)
Вообще мне понравилось как декомпозирован код. Узнал, что из Figma можно экспортировать дизайн в QT. Короче отличная олдскульная работа со своим авторским ui, когда ещё не было этих вездесущих Jupyter Notebook, которые выглядят одинаково как армейские сапоги.
В питоне, как таковых корутин нет, есть генераторы.
Корутина это абстрактное понятие (как функция, например). Генератор здесь скорее конкретный API. Какое-то время генераторы использовались в питоне для эмуляции корутин. Но с момента появления async/await в синтаксисе языка, у корутин теперь свой API: Coroutine наследует Awaitable, а не Generator - и набор методов у них отличается. Пруф. https://docs.python.org/3/library/collections.abc.html . Генераторы какое-то время можно было использовать в качестве корутин, но в python 3.11 это (декоратор asyncio.coroutine) уже выпилили.
Методом кнута и пряника )
Тестируем многоядерный процессор методом Кнута и Python’а