Хороший выбор алгоритма параллельной сортировки для выполнения в качестве домашнего задания?

Question

Я хочу реализовать быстрый алгоритм для домашней работы, но использую параллельную обработку для этой задачи.Я слышал, что параллельная версия Quicksort - лучший выбор, но я не уверен в этом ... может быть, Heapsort - хорошая идея.Какой алгоритм, по вашему мнению, является лучшим для параллельной среды и почему?

Answer 1

Быстрая сортировка может разбить несортированный список на две половины, но, к сожалению, не гарантируется, что эти половины будут где-то рядом.Таким образом, одна машина (или половина кластера машин) может получить 20 записей, а другая половина - 20 млрд.

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

Слияние типа - это то, что я думаю, вы хотите.

• Каждое разделение составляет ровно 50% списка, поэтому его легко разделить между процессорами.
• Вы можете реализовать сортировку слиянием на двух наборах ленточных накопителей, что означает, что не требуется, чтобы весь список был в памяти одновременно .Для больших списков, особенно тех, которые больше доступной памяти, это должно быть.
• Сортировка слиянием также стабильна в параллельных реализациях, если это имеет значение.

Answer 2

Сортировка слиянием - отличный метод параллельной сортировки.Наилучшая сортировка всегда зависит от машины и обычно включает в себя сочетание методов сортировки для входных данных разного размера.

Answer 3

Как отмечает Дин J , сортировка слиянием является хорошим кандидатом. Но у него есть недостаток: требуется синхронизация, когда оба потока завершены (процесс слияния).

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

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

Answer 4

Как насчет думать об этом в два этапа.

Шаг 1. Разбейте мои данные на N кусков, где N - это количество процессоров / узлов / ядер. Сортировать каждый кусок.

Шаг 2. Объедините мои N кусков вместе.

Для сортировки N фрагментов вы можете использовать все, что захотите, основываясь на ваших данных. Быстрая сортировка, heapsort, мне все равно. На втором этапе сортировка слиянием действительно хорошо объединяет два отсортированных списка, так что это, вероятно, ваш лучший выбор.

Answer 5

Вы должны рассмотреть Битоническая сортировка :

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

Битонные массивы можно объединять в отсортированные массивы очень хорошо распараллеливающим способом: хотя его общая временная сложность составляет O (n log (n)), все его сравнения и свопы независимы, т.е. выбор элементов длясравнение не зависит от предыдущих результатов сравнения, в отличие от обычного слияния.Следовательно, он допускает полное распараллеливание.

Это Youtube-видео демонстрирует битоническую сортировку.

PS - Я предполагаю, что домашняя работа автора уже должна ... 3 годаназад.

Answer 6

Я действительно некоторое время назад работал над алгоритмом параллельной сортировки для библиотеки распараллеливания и пришел к выводу, что это не стоит делать.Для небольших наборов данных стоимость даже нескольких примитивов синхронизации делает параллельную сортировку медленнее, чем обычная сортировка.Для больших наборов данных вы в основном ограничены пропускной способностью совместно используемой памяти и получаете минимальное ускорение.В случае сортировки большого числа (я думаю, 10 миллионов) целых чисел мне удалось получить ускорение в 1,5 раза только на двухъядерном процессоре, используя быструю параллельную сортировку IIRC.* Большая часть программирования, которое я делаю, заключается в обработке чисел, поэтому я склонен думать с точки зрения сортировки простых примитивов.Я все еще думаю, что параллельная сортировка - плохая идея для этих случаев.Однако если вы сортируете вещи, которые дорого сравнивать, этот ответ неприменим.

Answer 7

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