Java8 Arrays.sort VS Arrays.parallelSort应用实例源码教程。所有的开发者都会用到Arrays.sort来进行对象和原生数组进行排序,这个API会使用归并排序或者Tim排序来进行排序,源码如下所示:
1
2
3
4
5
6
|
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested) legacyMergeSort(a); else ComparableTimSort.sort(a); } |
上面的代码会依次执行,技术归并排序使用了分治的技术。Java8出来之后,有一个新API用来进行排序,这就是Arrays.ParallelSort,这是一种并行排序,有意思吧,让我们来看看它是怎么实现的。 Arrays.ParallelSort使用了Java7的Fork/Join框架使得排序任务可以在现场池中的多个线程中进行,Fork/Join实现了一种任务窃取算法,一个闲置的线程可以窃取其他线程的闲置任务进行处理。
Arrays.parallelSort概述
这个方法使用了一个临界值,还有一些容量小于这个临界值的数组,这个临界值和数组的容量都是计算来用于并行计算的,如下代码所示:
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/Join任务对排序后的数组进行合并。Java8使用如下的方法进行实现: 1、将数组分成4个子数组。 2、对前面两个子数组进行排序然后合并。 3、对后面的两个进行排序然后合并。 上面着几个步骤会重复递归,每个子数组都要求容量小于上面计算出来的临界值。
一些有意思的结果
我尝试去对比Arrays.sort和Arrays.parallelSort的排序时间,在一台4CPU的电脑上,使用如下的代码:
1
2
3
4
5
6
7
8
9
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 ); } } |
数组容量和时间消耗的一个基准测试如下所示:
在数组容量小于10000的情况下,并行排序和串行排序消耗时间是差不多的,但是当数组容量在10000以上的时候,并行排序就体现出了它的优势。