Многопоточная сортировка или слияние

Ответ 1

попробуйте 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/library/j-jtp03048.html?S_TACT=105AGX01&S_CMP=LP)

Ответ 2

Извините, но то, что вы просите, невозможно. Я считаю, что кто-то еще упомянул, что сортировка связана с 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();
                }
            }
        }
    }
}

Ответ 3

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

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

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

Ответ 4

Просто закодированный выше MergeSort, и производительность была очень плохой.

Блок кода ссылается на "coInvoke (левый, правый)"; но ссылка на это не была и заменила его invokeAll (слева, справа);

Код проверки:

MergeSort mysort = new MyMergeSort(array,0,array.length);
ForkJoinPool threadPool = new ForkJoinPool();
threadPool.invoke(mysort);

но пришлось остановить его из-за низкой производительности.

Я вижу, что статья выше почти год назад, и, возможно, теперь все изменилось.

Я нашел код в альтернативной статье для работы: http://blog.quibb.org/2010/03/jsr-166-the-java-forkjoin-framework/

Ответ 5

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

Ответ 6

Я столкнулся с проблемой многопоточного сортирования себя последние пару дней. Как объяснено на этом слайде caltech, лучшее, что вы можете сделать, просто используя многопоточность каждого шага разрыва и преодолевая подходы к очевидному числу потоков (число разделов) ограничено. Я предполагаю, что это связано с тем, что, хотя вы можете запускать 64 раздела по 64 потокам, используя все 64 ядра вашей машины, 4 деления могут выполняться только на 4 потоках, 2 на 2 и 1 на 1 и т.д. Так что для многих уровней рекурсии ваша машина недоиспользуется.

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

Iff, первые критерии вашей функции сортировки основаны на целочисленном максимальном размере s, будь то фактическое целое число или char в строке, так что это целое число или char полностью определяет наивысший уровень ваш вид, тогда я думаю, что есть очень быстрое (и простое) решение. Просто используйте это начальное целое, чтобы разделить проблему сортировки на более мелкие проблемы сортировки и отсортировать их по стандартным однопоточным сортировочным алгоритмом по вашему выбору. Думаю, деление на s-классы можно сделать за один проход. Проблема слияния не возникает после выполнения независимых видов, потому что вы уже знаете, что все в классе 1 сортируется до класса 2 и т.д.

Пример: если вы хотите сделать сортировку на основе strcmp(), используйте первый char в своей строке, чтобы разбить ваши данные на 256 классов, а затем отсортировать каждый класс в следующем доступном потоке, пока они не станут все сделал.

Этот метод полностью использует все доступные ядра, пока проблема не будет решена, и я думаю, что это легко реализовать. Я еще не реализовал его, но, возможно, с ним могут возникнуть проблемы, которые мне еще предстоит найти. Это явно не работает для видов с плавающей запятой и будет неэффективным для больших s. Его производительность также будет сильно зависеть от энтропии целого числа / char, используемого для определения классов.

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

Ответ 7

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