Параллельная сортировка в Java

Question

В настоящее время я работаю над программой для сортировки строк одновременно. Моя программа принимает файл, считывает каждую строку файла в массив и разбивает массив строк на меньшие массивы строк. Затем программа запускает один поток для каждого из меньших массивов и быстро сортирует их. Как только каждый поток завершил сортировку своего массива, основной поток собирает все результаты от объектов потока. Затем предполагается объединить меньшие, теперь отсортированные массивы в один большой сортированный массив.

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

Любая помощь приветствуется - заблаговременно.

Answer 1

Начало работы с окончательным merge процедура mergesort. Вы читаете первое значение каждого из ваших m-массивов (минимум одного подмассива), затем вы выбираете минимум m прочитанных значений (глобальный минимум), вставляете его в результат и удаляете из содержащего массива или увеличиваете соответствующий индекс на единицу. Затем, итерация до тех пор, пока все подмассивы не будут пустыми, или все индексы достигнут конца соответствующих массивов.

ПРИМЕЧАНИЕ. Это может уменьшить использование памяти, если у вас действительно большой набор данных (он фактически используется для обработки таких ситуаций), но может работать хуже, чем необработанный Quicksort beacause из стоимости разделения (который становится линейным, если вы копируете subarrays) и многопоточными служебными данными. Учтите, что в месте, где Mergesort более экономичен по площади при применении к крупным массивам. Подумайте также, что кто написал Quicksort, вы используете, вероятно, потраченное время, оптимизируя вызовы и выполнение ветвей.

Это базовая теоретическая CS, но обратите внимание, что вы не можете опустить класс сложности вычислений просто используя параллелизм, вы получаете только линейное ускорение . Наконец, Quicksort попадает в нижний предел средней сложности для алгоритмов сортировки сортировки: если вы пытаетесь превзойти Quicksort O(nlog(n)), у меня плохие новости для вас.

Answer 2

Я думаю, что использование сортировки слияния довольно стандартно.

Я предлагаю использовать столько потоков, сколько у вас есть для начала.

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

например. сортировка radix с TreeSets может быть быстрее, поскольку она будет сортироваться к моменту, когда вы прочитали файл.

Answer 3

Здесь вы можете использовать процедуру слияния. Алгоритм довольно прост, см. Merge sort о википедии. Использование может использовать простое двухстороннее слияние при объединении двух массивов или многократном слиянии при одновременном объединении нескольких массивов.

Также проверьте эту работу: Parallelized QuickSort and RadixSort with Optimal Speedup.

Наконец, есть также 3-way string quicksort, которые могут быть параллельны.

Answer 4

Как упоминалось в другом посте, последний шаг в вашем алгоритме - это объединение.

Однако сам quicksort является рекурсивным алгоритмом и позволяет естественное введение параллелизма, так что ваш «шаг слияния» устарел, см., Например,, http://ricardozuasti.com/2012/java-concurrency-examples-forkjoin-framework/

После того, как элемент поворота находится в своем последнем положении, вы вызываете быстрый сортировку по двум разделам. Это можно сделать одновременно. Поскольку это рекурсивно, он будет охватывать другие потоки.