Многопоточный quicksort или сортировка с объединением

Question

Многопоточный quicksort или сортировка с объединением

Как я могу реализовать параллельный quicksort или сортировать алгоритм с объединением для Java?

У нас были проблемы о (виртуальном) 16-ядра Mac, где только одно ядро (!) работало с помощью алгоритма сортировки Java по умолчанию, и было, ну, в общем, не хорошо видеть что очень прекрасная машина быть абсолютно недогруженным. Таким образом, мы записали наше собственное (я записал это), и мы действительно получали хорошие ускорения (я записал многопоточный quicksort и из-за его характера разделения, который это параллелизирует очень хорошо, но я, возможно, записал сортировку с объединением также)... Но моя реализация только увеличивается к 4 потокам, это - собственный код, и я использовал бы тот, прибывающий из уважаемого источника вместо того, чтобы использовать мое заново изобретенное колесо.

Единственный, который я нашел в сети, является примером того, как не записать многопоточный quicksort в Java, это - занятое цикличное выполнение (который действительно ужасен), использующий a:

while (helpRequested) { }

http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html

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

Следовательно мой вопрос: Вы знаете о каком-либо правильно многопоточном quicksort или сортируете реализацию с объединением в Java, который прибыл бы из уважаемого источника?

Я поставил акцент на том, что я знаю, что сложность остается O (n, регистрируют n), но я все еще наслаждался бы очень многим, чтобы видеть, что все эти ядра начинают работать вместо бездействия. Обратите внимание, что для других задач, на тех же самых 16 виртуальных ядрах Mac, я видел ускорение до x7 путем параллелизации кода (и я - значительным эксперт в параллелизме).

Таким образом, даже жесткий сложность остается O (n, регистрируют n), я был бы очень признателен за x7 или x8 или даже x16 ускорение.

25

java multithreading sorting quicksort mergesort

задан Raedwald 1 February 2016 в 07:59

3 ответа

Другие вопросы по тегам:

java multithreading sorting quicksort mergesort

Похожие вопросы:

score 21 · Answer 1

попробуйте вилку/совместную рамку Дага Леа:

public class MergeSort extends RecursiveAction {
    final int[] numbers;
    final int startPos, endPos;
    final int[] result;

    private void merge(MergeSort left, MergeSort right) {
        int i=0, leftPos=0, rightPos=0, leftSize = left.size(), rightSize = right.size();
        while (leftPos < leftSize && rightPos < rightSize)
            result[i++] = (left.result[leftPos] <= right.result[rightPos])
                ? left.result[leftPos++]
                : right.result[rightPos++];
        while (leftPos < leftSize)
            result[i++] = left.result[leftPos++];
        while (rightPos < rightSize)
        result[i++] = right.result[rightPos++];
    }

    public int size() {
        return endPos-startPos;
    }

    protected void compute() {
        if (size() < SEQUENTIAL_THRESHOLD) {
            System.arraycopy(numbers, startPos, result, 0, size());
            Arrays.sort(result, 0, size());
        } else {
            int midpoint = size() / 2;
            MergeSort left = new MergeSort(numbers, startPos, startPos+midpoint);
            MergeSort right = new MergeSort(numbers, startPos+midpoint, endPos);
            coInvoke(left, right);
            merge(left, right);
        }
    }
}

(источник: http://www.ibm.com/developerworks/java/library/j-jtp03048.html?S_TACT=105AGX01&S_CMP=LP)

score 0 · Answer 2

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

score -4 · Answer 3

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