Fork me on GitHub

Java sort和parallelSort接口及其实现

前言

上篇文章我们介绍了 排序算法(九)-Java源码中的DualPivotQuicksort,今天我们来看下sort接口的实现,看看JDK对数据排序这块到底做了哪些优化。

正文

sort接口

sort接口有多个重载的方法,我们整理下后,它们分别如下:

java.util.Arrays类里,调用 Array.sort(a)方法,可以对数组a进行排序,它有18个重载方法。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//整个int数组排序
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
//对int数组from到to的位置进行排序
public static void sort(int[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

//long数组
public static void sort(long[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(long[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

//short数组
public static void sort(short[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(short[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

//char数组
public static void sort(char[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(char[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

//byte数组
public static void sort(byte[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1);
}
public static void sort(byte[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
}

//float数组
public static void sort(float[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(float[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

//double数组
public static void sort(double[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
public static void sort(double[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
}

//Object数组
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
public static void sort(Object[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex);
else
ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}

//泛型数组
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
if (c == null) {
sort(a, fromIndex, toIndex);
} else {
rangeCheck(a.length, fromIndex, toIndex);
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex, c);
else
TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
}
}

源码分析

可以看到对于基本数据类型,因为排序稳定性不会对数据造成影响(两个一样的数据谁前谁后都可以),故使用了DualPivotQuicksort排序算法。

对于Object数组(没有继承Comparator接口的数据类型),会先判断一个LegacyMergeSort.userRequested的值是否为真,如果为真就使用legacyMergeSort排序算法,否则就使用ComparableTimSort排序算法。

对于泛型数组T [],如果比较器Comparator为空,就按照Object []方式进行处理;如果有比较器的话,照样先判断LegacyMergeSort.userRequested的值是否为真,是的话就用legacyMergeSort排序算法,否则就使用TimSort排序算法。

其他地方的sort最终会调用Array.sort(a)方法。如java.util.Collections类里的sort(List list)方法,最终调用了Array.sort(T[] a)

根据上面的分析,我们先来看看LegacyMergeSort.userRequested这个参数吧,因为它决定非基本数据类型数组到底是使用legacyMergeSort还是TimSort(ComparableTimSort是TimSort的Object []版本,也相当于TimSort)。

追踪源码,LegacyMergeSort.userRequested赋值过程如下:

1
2
3
4
5
6
static final class LegacyMergeSort {
private static final boolean userRequested =
java.security.AccessController.doPrivileged(
new sun.security.action.GetBooleanAction(
"java.util.Arrays.useLegacyMergeSort")).booleanValue();
}

可以看到它是可以通过系统设置进行配置的,java -Djava.util.Arrays.useLegacyMergeSort=true,可以设置使用老的归并排序。

这个值默认是false,即不使用归并排序,Java之所以有这部分判断,完全是为了兼容老版本,同时归并排序这部分将在未来移除(当前介绍版本为JDK1.8,在JDK11中发现已经移除)。

legacyMergeSort这个方法涉及到的就是归并排序,关于这部分,我们不再展示源码(Java未来版本也会移除),有兴趣的可以看看我之前的文章归并排序(MergeSort)部分。这两者唯一不同的是Java的legacyMergeSort在排序部分长度小于 INSERTIONSORT_THRESHOLD = 7 的时候,会使用插入排序,相当于提高了普通归并的效率。

TimSort或者ComparableTimSort我在之前文章中也有分析了,有兴趣的可以看看,这儿不过多介绍。排序算法(六)- TimSort

关于Java源码里的DualPivotQuicksort内容详见这篇文章排序算法(九)-Java源码中的DualPivotQuicksort

parallelSort接口

看完串行排序接口,我们再来看下Java自带排序的并行版本parallelSort接口,看看它是如何实现并行排序的。

先看看它的几个重载方法,由于基本数据类型数组的parallelSort都是类似的,这儿我只拿int[]进行举例。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//int数据并行排序方法(其它基本数据类型数组和其类似,这儿代码就不在展示)
public static void parallelSort(int[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJInt.Sorter
(null, a, new int[n], 0, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}
public static void parallelSort(int[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
else
new ArraysParallelSortHelpers.FJInt.Sorter
(null, a, new int[n], fromIndex, n, 0,
((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g).invoke();
}

//泛型数组并行排序方法(无比较器)
public static <T extends Comparable<? super T>> void parallelSort(T[] a) {
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, NaturalOrder.INSTANCE, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
}
public static <T extends Comparable<? super T>>
void parallelSort(T[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, fromIndex, toIndex, NaturalOrder.INSTANCE, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, NaturalOrder.INSTANCE).invoke();
}

//泛型数组并行排序方法(有比较器)
public static <T> void parallelSort(T[] a, Comparator<? super T> cmp) {
if (cmp == null)
cmp = NaturalOrder.INSTANCE;
int n = a.length, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, 0, n, cmp, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
0, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
}
public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> cmp) {
rangeCheck(a.length, fromIndex, toIndex);
if (cmp == null)
cmp = NaturalOrder.INSTANCE;
int n = toIndex - fromIndex, p, g;
if (n <= MIN_ARRAY_SORT_GRAN ||
(p = ForkJoinPool.getCommonPoolParallelism()) == 1)
TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0);
else
new ArraysParallelSortHelpers.FJObject.Sorter<T>
(null, a,
(T[])Array.newInstance(a.getClass().getComponentType(), n),
fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
MIN_ARRAY_SORT_GRAN : g, cmp).invoke();
}

源码分析

对于基本类型数组数据,并行排序会判断排序长度n(或者数组长度)是否小于 MIN_ARRAY_SORT_GRAN = 1 << 13 = 8192,如果小于或者p = ForkJoinPool.getCommonPoolParallelism()) == 1的时候,就会使用DualPivotQuicksort排序算法;否则它创建了一个ArraysParallelSortHelpers.FJInt.Sorter类进行并行排序。

对于Object数组或者泛型数组T[]的排序,可以看到与基本数据类型相似,只是最后的排序算法使用的是稳定的TimSort,并行帮助类使用的是ArraysParallelSortHelpers.FJObject.Sorter,这个类底层串行排序也是基于TimSort。

我们来分析下并行排序源码:

对于长度小于8192很好理解,就是数据长度小的时候,使用串行排序就可以了,即DualPivotQuicksort,并没有使用并行排序。

ForkJoinPool.getCommonPoolParallelism()是返回公共线程池的并行级别,即允许多少个线程并行,如果是1的话说明禁用了线程,那么就无法使用多线程,也就只能使用串行排序,关于这个值和ForkJoinPool相关,后面我们会看下这个类,来了解一下它的实现,这儿就不过多叙述。

我们重点来看下ArraysParallelSortHelpers.FJInt.Sorter这个类,这个是针对于int数组的并行工具类,当然我们还可以看到其它数据类型的并行工具类,如ArraysParallelSortHelpers.FJByte.Sorter,他们都在ArraysParallelSortHelpers这个类里。

这个类的并行实现是根据Cilk算法来实现的。

Cilk是一种多线程算法语言。Cilk背后的理念是,程序员应该集中精力构建程序,以暴露并行性和利用局部性,让Cilk的运行时系统负责调度计算,以便在给定平台上高效运行。因此,Cilk运行时系统负责诸如负载平衡、分页和通信协议等细节。然而,与其他多线程语言不同,Cilk是算法语言,因为运行时系统保证了高效和可预测的性能。

算法内容大致如下:

  1. 如果数组长度 n 过小(小于临界值 threshold ),就使用串行排序;
  2. 否则,将数组分为两半:

    • 将一半数组再分为两半(n/4),对于每一半,继续分割下去,直到数组长度小于临界值threshold,不再进行分割;
    • 对前一半串行排序,对后一半串行排序,两半排序是并行进行的;
    • 需要注意的是 n/2排序时需要保证两个n/4的并行排序合并完成,以此类推,n/4排序时需要保证两个n/8的并行排序合并完成……
    • 将两部分合并

其伪代码大致如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void parallelSort(int[] a,int low,int high){
int n = high - low +1;
if(n < threshold){
sort(a);
}else{
int half = n >>>1;
ForkJoinTaskTest task1 = ForkJoinTaskTest(a,low,half-1);
task1.fork();
ForkJoinTaskTest task2 = ForkJoinTaskTest(a,half,high-1);
task2.compute();
task1.join();
merge(a,low,half,high-1);
}
}

可以看到这个分割过程和我们之前说到过的 双调排序的并行版本有些许类似。

我们先不看Java源码的相关实现,我们想,如果我们自己实现一个并行版本的排序如何实现呢?

我们需要使用到ForkJoinPool,我们可以参考我的另一篇文章一道Java试题引发的思考

这篇文章里使用了分支/合并框架(ForkJoinPool)来使用并行处理累加数据,我们参照这个模式,可以根据伪代码写出使用 Java DualPivotQuicksort的并行版本,如下:

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
public class ParallelSort {
public static void main(String[] args) throws Exception {
int[] a = new int[100000000];
Random r = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(100000000);
}
int[] b = a.clone();
System.out.println("ParallelSort排序开始:");
long start = System.currentTimeMillis();
ForkJoinParallelSort task = new ForkJoinParallelSort(a);
new ForkJoinPool().invoke(task);
System.out.println("ParallelSort耗时:" + (System.currentTimeMillis() - start) + "ms");
System.out.println("ParallelSort排序完成!");
System.out.println("数组是否有序:" + isOrdered(a));

System.out.println("ArrayParallelSort排序开始:");
long start1 = System.currentTimeMillis();
Arrays.parallelSort(b);
System.out.println("ArrayParallelSort耗时:" + (System.currentTimeMillis() - start1) + "ms");
System.out.println("ArrayParallelSort排序完成!");
System.out.println("数组是否有序:" + isOrdered(b));
}
}

class ForkJoinParallelSort extends RecursiveTask<Void> {
/**
* 要排序的数组
*/
private final int[] array;
/**
* 数组起始下标
*/
private final int start;
/**
* 数组结束下标
*/
private final int end;
/**
* 数组最小长度
*/
public static final int THRESHOLD = 8192;

public ForkJoinParallelSort(int[] array) {
this(array, 0, array.length - 1);
}

private ForkJoinParallelSort(int[] array, int start, int end) {
this.array = array;
this.start = start;
this.end = end;
}

@Override
protected Void compute() {
int length = end - start + 1;
int half = length >>> 1;

//小于等于阈值,串行排序处理
if (length <= THRESHOLD) {
computeSequentially(array, start, end);
return null;
}
//创建一个子任务来为数组的前一半排序
ForkJoinParallelSort leftTask = new ForkJoinParallelSort(array, start, start + half - 1);
//利用另一个ForkJoinPool线程异步执行新创建的子任务
leftTask.fork();
//创建一个任务为数组的后一半排序
ForkJoinParallelSort rightTask = new ForkJoinParallelSort(array, start + half, end);
//同步执行第二个子任务,有可能允许进一步递归划分
rightTask.compute();
//读取第一个子任务的结果,没有完成就等待
leftTask.join();
//合并结果
//long startTime = System.currentTimeMillis();
merge(array, start, start + half - 1, start + half, end);
//System.out.println("耗时:"+(System.currentTimeMillis()-startTime)+"ms");
return null;
}
/**
* 使用JavaDualPivotQuickSort串行处理较小的数组
*
* @return
*/
private void computeSequentially(int[] array, int start, int end) {
//直接调用Arrays.sort 也可以
JavaDualPivotQuicksort.sort(array, start, end, null, 0, 0);
}
/**
* 快速合并两个有序数组 O(min(m,n))
*
* @param array
* @param leftStart
* @param leftEnd
* @param rightStart
* @param rightEnd
*/
private void merge(int[] array, int leftStart, int leftEnd, int rightStart, int rightEnd) {
if (array[leftEnd] <= array[rightStart]) {
return;
}
int i = leftStart;
int j = rightStart;
int k = 0;
int len1 = leftEnd - leftStart + 1;
int len2 = rightEnd - rightStart + 1;
int[] temp = new int[len1 + len2];
while (i <= leftEnd && j <= rightEnd) {
if (array[i] <= array[j]) {
temp[k++] = array[i++];
} else {
temp[k++] = array[j++];
}
}
if (i == leftEnd + 1 && j <= rightEnd) {
System.arraycopy(array, j, temp, k, rightEnd - j + 1);
}
if (j == rightEnd + 1 && i <= leftEnd) {
System.arraycopy(array, i, temp, k, leftEnd - i + 1);
}
//处理完后将temp赋值给array
System.arraycopy(temp, 0, array, leftStart, len1);
System.arraycopy(temp, len1, array, rightStart, len2);
}
}

上述代码是比较好理解的,其要注意的地方是在排完序的两个有序数组合并上。

运行一下可以看到对于1亿数据量该方法耗时稳定在6~7s,Java源码的ParallelSort方法耗时在3~4s左右。

它们结果如下图:

upload successful

可以看到Java源码的排序处理速度要比我们实现的更高效的,速度差异主要在哪儿呢?

其实Java并行源码中借鉴了Cilk算法,但是有些不同的地方是,会把原数组分成四份进行并行排序。

算法说明如下:

  1. 将数组分成4个子数组。
  2. 对前面两个子数组进行排序然后合并。
  3. 对后面的两个进行排序然后合并。
    上面着几个步骤会重复递归,每个子数组都要求容量小于上面计算出来的临界值。

我们回到ArraysParallelSortHelpers这个类从它里面的FJInt这个类入手,其他的类的实现和其类似。

upload successful

upload successful

upload successful

根据上图的一些介绍,我再简单说明下。

其实上面图中Java源码这段代码是相当晦涩的,我们如何看出它每次是拆分成4个子任务并处理的呢?

我们可以根据第一次调用来看,这时候代码中的b = this.base = 0wb = this.wbase = 0,则三个Sorter如下:

1
2
3
new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();

代入b =0 可以看到,它们分别处理了[ u , u + n - u ],[ h , h + q ],[ q , q + h -q ] 三部分,正好是[ 3/4 , 1 ],[ 1/2 , 3/4 ],[ 1/4 , 1/2 ] 三部分。

而对于剩下的1/4 ,直接在当前线程处理(不需要fork),代码如下:

1
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);//注:此时 n = q (对于当前线程),可以看源码的赋值过程

分别排序完了,需要进行合并,如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
while (n > g) {
int h = n >>> 1, q = h >>> 1, u = h + q; // quartiles
Relay fc = new Relay(new Merger(s, w, a, wb, h, wb+h, n-h, b, g));
Relay rc = new Relay(new Merger(fc, a, w, b+h, q,b+u, n-u, wb+h, g));
new Sorter(rc, a, w, b+u, n-u, wb+u, g).fork();
new Sorter(rc, a, w, b+h, q, wb+h, g).fork();;
Relay bc = new Relay(new Merger(fc, a, w, b, q,b+q, h-q, wb, g));
new Sorter(bc, a, w, b+q, h-q, wb+q, g).fork();
s = new EmptyCompleter(bc);
n = q;
}
DualPivotQuicksort.sort(a, b, b + n - 1, w, wb, n);
s.tryComplete();

这段Relay的依存关系是 rc (合并后1/2部分)和 bc (合并前1/2部分) 是并行的,fc 会合并rc和bc (排序好的数据)。

Java中把并行分成四份的优势在哪里呢?

明显这段代码和使用我们Cilk算法每次分成两份的本质是一样的,而且分成4份代码变得更加晦涩。

具体原因就要说说这个Merger了,这个Merger是关于两个有序数组并行合并的实现,它的效率是非常高的,我们回到我们自己实现的那个ParallelSort类,可以看到我们设计的merge就是比较常规的合并,当两个数组数据量越大时,耗时越长,我在代码中注掉了耗时计算,有兴趣的童鞋可以打开观察下,在数据量较小情况下,其耗时基本是0~10ms,但是运行中随着两部分待合并的数据越来越大,耗时越来越大。

比如对于1亿数据的排序,其耗时主要消耗在2个5000w的数据合并成最终结果、4个2500w的数据两两合并成2个5000w数据、8个1250w的数据两两合并成4个2500w数据……的合并上。

Java中的这个Merger对合并进行了优化,使用了并行合并,其原理如下:

  1. 对于两个待合并数组A,B;
  2. 找到较大(或等于)的一个数组(比如A),如果长度小于阈值8192,就不分割了;如果大于8192,找到较大数组A的中点作为切割点M,使用二分法找到较小数组B中比这个切割点大的最小位置索引P;
  3. 这时候其实我们可以发现A中[lowA , M]和B中[lowB , P]位置数据合并后是始终 小于等于 A中[M , highA]和B中[P , highB]位置数据合并的,这就是分割合并有序的原则;
  4. 如果长度比较大,还会继续并行分割下去;
  5. 然后我们对上面拆分的数据两两合并,最终多线程执行完也就得到了有序数据。

有兴趣的童鞋可以参考原理结合上图看一下。

而我们在排序及合并时,会用到工作数组,分成4份后,可以保证最后的排序完成数组在原数组中,而不是在工作数组中,也避免了一次数据拷贝。

总结

关于Java自带排序的内容就介绍到这儿,可以看到相比于串行排序,并行排序更加复杂,但是Cilk并行算法的原理还是比较简单的,Java并排代码之所以复杂是因为它尽可能的优化了算法耗时。

这也是软件开发者应当具有的品质:精益求精。

源码

关于自写的ParallelSort排序可见于我的 GitHub

关于 ArraysParallelSortHelpers相关代码可以参考JDK源码(1.8及以上版本)。

参考资料

  • JDK ArraysParallelSortHelpers源码
  • JDK Arrays源码



-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

SakuraTears wechat
扫一扫关注我的公众号
您的支持就是我创作的动力!
0%