В предыдущем посте я писал о комбинаторном объекте, известном как латинский квадрат. Я также обсудил некоторые исследования, которые я ранее провел, и некоторые направления исследований для работы с этими объектами. В частности, я упоминаю о необходимости эффективных алгоритмов для генерации и обработки этих объектов. Одной из целей моей будущей работы было найти отображение, которое будет принимать значения латинского квадрата n x n, где n — порядок латинского квадрата, и отобразить их. к числу, в идеале такому, которое может быть представлено относительно небольшим количеством битов.

Недавно я пробовал разные формулы для определения такого числа и создал скрипт Python для проверки разных формул. Для небольших порядков латинских квадратов, которых не так много, это работало просто отлично и до порядка 5 работало разумно (завершение процесса ~8 минут). Однако существует множество латинских квадратов 6-го порядка (более 1 000 000 упрощенных латинских квадратов по нашему определению), проверка которых заняла ~6,5 часов. Это привело к поиску способов быстрого ускорения алгоритма, что мне удалось сделать с помощью многопроцессорной библиотеки Python.

В этом посте я представлю библиотеку многопроцессорной обработки в Python на очень простом примере, который дает общий обзор ее использования. Я также включу последовательную и многопроцессорную версии моего скрипта Python, чтобы показать, как это можно легко реализовать в любом приложении.

Краткий обзор многопроцессорной библиотеки

Многопроцессорная библиотека Python3 — это пакет, используемый для порождения процессов, подобных библиотеке потоков. В этом посте для параллелизма будет использоваться только пул, поскольку он прост в использовании и упрощает реализацию базовых потоков. В качестве примера представьте, что вам нужно возвести в квадрат первые 10 000 000 целых чисел, начиная с 0. Чтобы реализовать это последовательно, код Python может выглядеть так:

При использовании multiprocessing.Pool требуется совсем немного дополнительной работы для параллельного запуска.

Как видно здесь, добавив всего пару строк кода, мы успешно сделали это многопроцессорное приложение. Основное отличие заключается в модификации этих двух рядов

В последнем коде (т. е. многопроцессорном коде) объект multiprocessing.Pool создается с числом, переданным для представления количества процессов, которые нужно создать. Затем вызывается Pool.map() для сопоставления значений в списке чисел ( values) с вызываемой функцией ( square). Все остальное обрабатывается многопроцессорной библиотекой и операционной системой.

Следует отметить, что if __name__ == '__main__': является более или менее обязательным, поскольку сценарий выдаст ошибку из-за того, как обрабатываются процессы и порожденные процессы, по крайней мере, это ошибка, когда Я запускал его в системе Windows.

Запуск последовательного сценария для 10 000 000 номеров завершен примерно за 1,69 секунды. Параллельный сценарий завершен примерно за 1,98 секунды. Это подчеркивает важный аспект распараллеливания приложения: не все приложения следует запускать с несколькими потоками/процессами. Хотя этот простой пример дает хорошее представление о том, как можно быстро использовать библиотеку многопроцессорной обработки для повышения производительности, накладные расходы от многопоточности заняли больше времени, чем было сэкономлено за счет создания нескольких процессов.

Реальное приложение

Как упоминалось во введении, недавно я использовал библиотеку многопроцессорной обработки в созданном мной инструменте Python и, в отличие от приведенного выше примера, увидел значительный прирост производительности. Ниже приведен серийный код, который я использовал

Природа приведенного выше кода на самом деле не важна. Поскольку большинство читателей не знают (или не интересуются), что такое латинский квадрат, я постараюсь сосредоточиться на реализации многопроцессорной обработки и обсуждении прироста производительности. Для тех, кому интересно, я добавил несколько редких комментариев по всему коду, чтобы помочь описать, что происходит.

В реализации многопроцессорной обработки будут задействованы две вещи: определение значения, представляющего каждый латинский квадрат, и обработка, которая определяет, является ли каждое значение уникальным, последнее требует гораздо больше времени.

Чтобы использовать класс multiprocessing.Pool, у нас должны быть функции, с которыми Pool.map() может отображать значения в предоставленном списке. Итак, для начала мы вытаскиваем части кода, которые мы хотим запустить с более чем одним процессом, в отдельные функции.

Здесь первая функция определяет число, которому сопоставлен латинский квадрат, а вторая объединяет результаты в словарь, попутно проверяя наличие дубликатов.

Теперь, когда эта функциональность разделена на функции, мы можем использовать библиотеку многопроцессорности для ускорения алгоритма.

Это довольно много кода, поэтому я выделю самую важную часть, то есть реализацию многопроцессорности.

Еще раз создается объект multiprocessing.Pool, на этот раз с 20 процессами, доступными для пула, так как я запускаю его на моем сервере. Комментарии довольно хорошие, но для большей полноты один и тот же пул процессов используется для сопоставления функции get_value с каждым квадратом в файле ( объект lines = список строк, представляющих латинские квадраты) и создать список словарей с помощью функции build_dict. Эта последняя функция на самом деле занимала большую часть времени обработки последовательного сценария.

Результаты производительности

Результаты последовательного скрипта показаны в таблице ниже.

Сценарий занимает невероятное количество времени! Не только это, но и по мере того, как заказ увеличивается (немного), время его выполнения занимает намного больше времени. Это связано с тем, что количество латинских квадратов растет комбинаторно по мере увеличения порядка латинского квадрата, представьте себе, что это нужно запускать для порядков 8, 9 или 10! (Запуск сценария для любого из этих заказов, вероятно, займет достаточно много времени, чтобы сделать его непрактичным.) Давайте посмотрим на результаты с добавлением многопроцессорности.

Создание 20 процессов сделало время выполнения этого скрипта проверки более управляемым. Для заказа 6, который занял более 6 часов при серийном запуске, сценарий завершился за 2,14 минуты, что является существенным улучшением. То же самое можно сказать и о заказе 5, время выполнения которого сократилось прибл. 8 минут до 3,75 секунды. Мы также можем видеть здесь, что накладные расходы на многопроцессорность превышают скорость при использовании многих процессов для порядка 4, поскольку время выполнения увеличилось с 0,025 секунды до 0,13 секунды. В любом случае время выполнения достаточно быстрое, чтобы не иметь большого значения.

Заключение

В этом посте я кратко рассказал о многопроцессорной библиотеке Python, в частности об объекте multiprocessing.Pool. Пул позволяет любому разработчику быстро улучшить время выполнения медленных алгоритмов, часто добавляя всего несколько строк кода. Я привел небольшой пример (который не выиграл от многопроцессорности), а также реальное приложение, которое значительно выиграло от небольших изменений в его реализации. Аналогичным образом я использовал многопроцессорную библиотеку для обработки новостных статей для моего исследовательского сайта ntrinsically.com, который каждый час выполняет анализ тональности тысяч новостных статей. Существует множество приложений для этой простой в использовании библиотеки, и я надеюсь, что эта статья помогла вам реализовать многопроцессорность или, по крайней мере, продемонстрировала, как ее можно использовать в реальных условиях.

Первоначально опубликовано на https://www.anthonymorast.com 8 января 2022 г.