Хороший выбор алгоритма параллельной сортировки для реализации в качестве домашней работы?
Я хочу реализовать быстрый алгоритм для домашней работы, но используя параллельную обработку для этой задачи. Я слышал, что параллельная версия Quicksort - лучший выбор, но я не уверен в этом ... возможно, Heapsort - хорошая идея. Какой алгоритм, по вашему мнению, лучше всего подходит для параллельной среды и почему?
5 ответов
Быстрая сортировка может разделить несортированный список на две половины, но, к сожалению, не гарантируется, что половинки будут хотя бы близко друг к другу. Таким образом, одна машина (или половина кластера машин) может получить 20 записей, а другая половина — 20 миллиардов.
Я не могу придумать, как заставить пирамидальную сортировку работать параллельно. Это можно сделать, но, чувак, это кажется действительно нелогичным.
Сортировка слиянием — это то, что, я думаю, вам нужно.
- Каждое разделение составляет ровно 50% списка, поэтому его легко разделить между процессорами.
- Вы можете реализовать сортировку слиянием на двух наборах ленточных накопителей, что означает, что не требуется, чтобы весь список был в памяти одновременно. Для больших списков, особенно тех, которые больше доступной памяти, это необходимо.
- Сортировка слиянием также стабильна в параллельных реализациях, если это имеет значение.
Как Дин Дж. упоминает, сортировка слиянием является хорошим кандидатом. Но у него есть недостаток, заключающийся в том, что требуется синхронизация, когда оба потока выполнены (процесс слияния).
Хотя у быстрой сортировки есть недостаток, заключающийся в том, что она непредсказуема при разбиении на разделы, что можно сделать, так это заставить первый раздел (определяющий загрузку процессора) сознательно разделить нагрузку более или менее равномерно, а затем позволить алгоритму идти своим чередом.
Преимущество заключается в том, что вам не нужно выполнять какую-либо синхронизацию после того, как процессоры закончат свою работу. После того, как они будут выполнены, у вас будет готовый отсортированный массив без необходимости дополнительного шага слияния, который может быть дорогостоящим.
Сортировка слиянием — отличный первый метод параллельной сортировки. Наилучшая сортировка всегда зависит от машины и обычно включает комбинацию методов сортировки для входных данных разного размера.
быстрая сортировка является рекурсивной, простой способ сделать любой рекурсивный алгоритм параллельным (только если он включает два или более рекурсивных вызова, как это делает быстрая сортировка) состоит в том, чтобы создать два новых потока для рекурсивных вызовов. и подождите, пока они не будут выполнены, а затем завершите свою функцию. это ни в коем случае не оптимально, но это довольно быстрый и грязный способ распараллеливания рекурсивных вызовов.
Как насчет того, чтобы подумать об этом в два этапа.
Шаг 1. Разбейте мои данные на N фрагментов, где N — количество процессоров/узлов/ядер. Отсортируйте каждый кусок.
Шаг 2. Объедините мои N кусков вместе.
Для сортировки N фрагментов вы можете использовать все, что захотите, исходя из ваших данных. Быстрая сортировка, пирамидальная сортировка, мне все равно. Для шага 2 сортировка слиянием очень хорошо обрабатывает объединение двух отсортированных списков, так что это, вероятно, ваш лучший выбор.