Как реализовать многопоточный Mergesort на Java [duplicate]

дают попытку fork / join framework Doug Lea :

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 / библиотека / J-jtp03048.html S_TACT = 105AGX01 & амп;? S_CMP = ЛП )

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

Java 8 предоставляет java.util.Arrays.parallelSort , который сортирует массивы параллельно с использованием инфраструктуры fork-join. Документация содержит некоторые сведения о текущей реализации (но это ненормативные заметки):

Алгоритм сортировки представляет собой параллельное сортирование-слияние, которое разбивает массив на под-массивы, которые сами сортируются и затем сливается. Когда длина поддиапазона достигает минимальной детализации, подматрица сортируется с использованием соответствующего метода Arrays.sort. Если длина указанного массива меньше минимальной гранулярности, то она сортируется с использованием соответствующего метода Arrays.sort. Алгоритм требует рабочего пространства, не превышающего размер исходного массива. Общий пул ForkJoin используется для выполнения любых параллельных задач.

Кажется, что не существует соответствующего метода параллельной сортировки для списков (хотя списки RandomAccess должны воспроизводиться хорошо с сортировкой), поэтому вам нужно будет использовать toArray, отсортировать этот массив и сохранить результат обратно в список. (Я задал вопрос об этом здесь .)

Извините, но то, что вы просите, невозможно. Я считаю, что кто-то еще упомянул, что сортировка связана с IO, и они, скорее всего, верны. Код от IBM от Doug Lea - приятная работа, но я считаю, что он предназначен в основном как пример того, как писать код. Если вы заметили в своей статье, он никогда не размещал для этого ориентиры и вместо этого размещал контрольные показатели для другого рабочего кода, например, вычисляя средние значения и находив минимальный максимум параллельно. Вот что такое тесты, если вы используете общую сортировку сортировки, быстрого сортировки, сортировки по Dougs Merge Sort, используя пул Join Fork Pool, и тот, который я написал, используя Quick Sort Join Fork Pool. Вы увидите, что Merge Sort является лучшим для N из 100 или меньше. Быстрый Сортировка для 1000 до 10000, а Быстрый Сортировка с использованием Присоединительного пула Винирует все остальное, если у вас есть 100000 и выше. Эти тесты состояли из массивов случайных чисел, которые выполнялись 30 раз, чтобы создать среднее значение для каждой точки данных и выполнялись на четырехъядерном ядре с примерно 2 гигабайтами. И ниже у меня есть код для быстрого сортировки. Это в основном показывает, что, если вы не пытаетесь отсортировать очень большой массив, вам следует отказаться от попытки улучшить алгоритм сортировки ваших кодов, поскольку параллельные работают очень медленно на небольших N.

Merge Sort
10  7.51E-06
100 1.34E-04
1000    0.003286269
10000   0.023988694
100000  0.022994328
1000000 0.329776132


Quick Sort
5.13E-05
1.60E-04
7.20E-04
9.61E-04
0.01949271
0.32528383


Merge TP
1.87E-04
6.41E-04
0.003704411
0.014830678
0.019474009
0.19581768

Quick TP
2.28E-04
4.40E-04
0.002716065
0.003115251
0.014046681
0.157845389

import jsr166y.ForkJoinPool;
import jsr166y.RecursiveAction;

//  derived from
//  http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html
//  Copyright © 2007, Robert Sedgewick and Kevin Wayne.
//  Modified for Join Fork by me hastily. 
public class QuickSort {

    Comparable array[];
    static int limiter = 10000;

    public QuickSort(Comparable array[]) {
        this.array = array;
    }

    public void sort(ForkJoinPool pool) {
        RecursiveAction start = new Partition(0, array.length - 1);        
        pool.invoke(start);
    }

    class Partition extends RecursiveAction {

        int left;
        int right;

        Partition(int left, int right) {
            this.left = left;
            this.right = right;
        }

        public int size() {
            return right - left;
        }

        @SuppressWarnings("empty-statement")
        //void partitionTask(int left, int right) {
        protected void compute() {
            int i = left, j = right;
            Comparable tmp;
            Comparable pivot = array[(left + right) / 2];

            while (i <= j) {
                while (array[i].compareTo(pivot) < 0) {
                    i++;
                }
                while (array[j].compareTo(pivot) > 0) {
                    j--;
                }

                if (i <= j) {
                    tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                    i++;
                    j--;
                }
            }


            Partition leftTask = null;
            Partition rightTask = null;

            if (left < i - 1) {
                leftTask = new Partition(left, i - 1);
            }
            if (i < right) {
                rightTask = new Partition(i, right);
            }

            if (size() > limiter) {
                if (leftTask != null && rightTask != null) {
                    invokeAll(leftTask, rightTask);
                } else if (leftTask != null) {
                    invokeAll(leftTask);
                } else if (rightTask != null) {
                    invokeAll(rightTask);
                }
            }else{
                if (leftTask != null) {
                    leftTask.compute();
                }
                if (rightTask != null) {
                    rightTask.compute();
                }
            }
        }
    }
}