Мы все использовали Arrays.sort для сортировки объектов и примитивных массивов. Этот API использовал сортировку слиянием ИЛИ Tim Sort для сортировки содержимого, как показано ниже:
|
1
2
3
4
5
6
|
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested) legacyMergeSort(a); else ComparableTimSort.sort(a);} |
Все это делается последовательно, хотя сортировка слиянием использует технику «разделяй и властвуй», все это делается последовательно. В Java 8 появился новый API для сортировки, который называется Arrays #rallelSort . Это делает сортировку параллельно. Интересное право! Давайте посмотрим, как это происходит …
Массивы # parallelSort использует инфраструктуру Fork / Join, представленную в Java 7, для назначения задач сортировки нескольким потокам, доступным в пуле потоков. Это называется есть свою собачью еду . Fork / Join реализует алгоритм кражи работы, при котором в свободном потоке можно красть задачи, поставленные в очередь в другом потоке.
Обзор массивов # parallelSort:
Метод использует пороговое значение, и любой массив размером меньше порогового значения сортируется с помощью API Arrays # sort () (т.е. последовательная сортировка). И порог рассчитывается с учетом параллельности машины, размера массива и рассчитывается как:
|
1
2
3
4
5
|
private static final int getSplitThreshold(int n) { int p = ForkJoinPool.getCommonPoolParallelism(); int t = (p > 1) ? (1 + n / (p << 3)) : n; return t < MIN_ARRAY_SORT_GRAN ? MIN_ARRAY_SORT_GRAN : t;} |
После того, как было решено, следует ли сортировать массив параллельно или последовательно, теперь нужно решить, как разделить массив на несколько частей, а затем назначить каждую часть задаче Fork / Join, которая позаботится о ее сортировке, а затем другой Fork /. Присоединитесь к задаче, которая позаботится о слиянии отсортированных массивов. Реализация в JDK 8 использует этот подход:
— Разделите массив на 4 части.
— Сортировать первые две части, а затем объединить их.
— Сортировка следующих двух частей, а затем объединить их.
И вышеупомянутые шаги повторяются рекурсивно с каждой частью, пока размер части для сортировки не будет меньше порогового значения, вычисленного выше.
Некоторые интересные результаты:
Я попытался сравнить время, затрачиваемое на Arrays # sort и Arrays #rallelSort на машине с 4 процессорами. Программа, которую я использовал для этого сравнения:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
public class ArraysParallelDemo { public static void main(String[] args) throws FileNotFoundException { List<Double> arraySource = new ArrayList<>(); Scanner reader = new Scanner(ClassLoader. getSystemResourceAsStream("java8demo/large_array_input")); while(reader.hasNext()){ String line = reader.nextLine(); String[] strNums = line.split(","); for ( String strN : strNums){ arraySource.add(Double.parseDouble(strN)); } } System.out.println(arraySource.size()); Double [] myArray = new Double[1]; myArray = arraySource.toArray(myArray); long startTime = System.currentTimeMillis(); Arrays.sort(myArray); long endTime = System.currentTimeMillis(); System.out.println("Time take in serial: "+ (endTime-startTime)/1000.0); Double [] myArray2 = new Double[1]; myArray2 = arraySource.toArray(myArray); startTime = System.currentTimeMillis(); Arrays.parallelSort(myArray2); endTime = System.currentTimeMillis(); System.out.println("Time take in parallel: "+ (endTime-startTime)/1000.0); }} |
Время, затраченное каждым из API на массивы двойных значений разных размеров, показано ниже:
Для списков существует аналогичная реализация, и многие операции над списками имеют параллельный эквивалент.