Многопоточный quicksort или mergesort

Question

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

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

только один я нашел в Интернете является примером того, как не писать многопоточные быстрой сортировки в Java, он занят, зацикливание (который на самом деле страшно) с помощью:

while (helpRequested) { } 

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

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

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

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

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

Answer 1

дать попробовать на fork/join framework by 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)

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

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

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

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

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

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

Answer 6

Только что закодированный выше 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/

Answer 7

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

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

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