java - Быстрый параллельный сортировка для ввода целых чисел без знака?

Question

Я нахожусь в задаче сортировки нескольких больших массивов неподписанных, 64-битных, случайных генерируемых целых чисел (более 5E7 элементов). Можете ли вы направить меня на параллельный алгоритм сортировки, который может проявлять почти линейное ускорение, по крайней мере, в случае случайных данных?

Я работаю с Java, если это имеет какое-то значение в отношении быстрой сортировки.

Редактировать: Обратите внимание, что этот вопрос в первую очередь касается параллельных сортов, способных достичь почти линейного ускорения. (Значение, когда количество исполняющих ядер растет из P к 2P, время, затраченные на параллельной сортировке падает до 55 -. 50 процентов расчета, выполненных на P ядер)

Answer 1

Ну если вы получил много памяти, вы можете использовать Bucketsort. Еще один алгоритм, который хорошо сочетается с параллелизмом является Quicksort

Answer 2

Из статьи Википедии на Quicksort,

Как сортировка слиянием, быстрая сортировка может быть также распараллеливание из-за его разделяй и властвуй природы. Отдельные операции с локальным разделом трудно распараллелить, но после их разделения разные разделы список можно сортировать параллельно. Ниже приведен простой подход : если у нас есть процессоры, мы можем разделить список элементов на подсписные числа в среднем времени O (n), а затем отсортировать каждое из них в среднем . Игнорируя время предварительной обработки и слияния O (n), это линейное ускорение. Если сплит слепой, игнорируя значения, слияние наивно стоит O (n). Если разделенные разделы, основанные на последовательности , поворачиваются, сложно распараллелить и наивно стоить O (n). Учитывая O (log n) или больше процессоров, требуется только O (n) время, , тогда как подход с линейным ускорением достигнет времени O (log n) для общего.

Очевидно, что объединение является другой альтернативой. I думаю, quicksort дает лучшие средние характеристики.

Answer 3

Быстрый сортировка и сортировка слияния довольно легко распараллеливаются. Oracle имеет целочисленное объединение типа fork/join here, которое вы, вероятно, могли бы использовать (если не как-есть, то, по крайней мере, как вдохновение).

Answer 4

Скажите, что у вас есть несколько компьютеров (5 на кластере Amazon?), И вы хотите восходящую сортировку. Разделите свой массив на более мелкие куски, чтобы он соответствовал каждой машине. Предполагая, что у вас есть n кусков/массивов. Попросите каждую машину быстро съесть свой кусок. Эта сортировка будет параллельна (более или менее в зависимости от размера блока и скорости машины и т. Д.).

Когда закончите сориентирование, попросите машины слить куски;

Вы можете сделать это 2 способами:

• 2 машины в то время (вы создаете слияние дерева). Слияние произойдет снова, параллельно.Проблема в том, что массив станет большим из-за слияния, и вам придется кэшировать на диск, поэтому, когда вы снова объединяетесь, машина читает с диска. Так что некоторые штрафы здесь.
• Вы можете делать n машин за раз. У вас есть одна машина координатора, которая берет мин из всех массивов других машин. Таким образом, машина-координатор создает весь отсортированный массив, беря наименьшее число из каждого из отсортированных массивов.

Answer 5

Bitonic sort - это алгоритм, предназначенный для параллельных машин. Вот вам sequential Java version и parallel C++ version, чтобы помочь вам начать работу.