本文为原创文章，转载请注明出处
查看[Java]系列内容请点击：https://www.jianshu.com/nb/45938443
fork-join框架会使用空闲线程来抢占当前线程的任务，具体实现原理这里就不说了，有兴趣的同学也可以自己实现一个。这里使用该框架进行归并排序，并对比普通的归并排序的效率：
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
public class Test {
private static final ForkJoinPool pool = new ForkJoinPool(4); // N 核心处理器
private static int[] merge; // 合并用
public static void main(String[] args) {
int len = 1000000; // 100万个数字排序
int sortTimes = 200; // 排序次数
merge = new int[len];
// 正常排序
long t1 = System.currentTimeMillis();
for (int t = 0; t < sortTimes; t++) {
normalSort(prepareData(len));
}
long t2 = System.currentTimeMillis();
System.out.println("正常排序共耗时：" + (t2 - t1) / 1000.0 + " 秒");
// 多线程排序
t1 = System.currentTimeMillis();
for (int t = 0; t < sortTimes; t++) {
multiThreadSort(prepareData(len));
}
t2 = System.currentTimeMillis();
System.out.println("多线程排序共耗时：" + (t2 - t1) / 1000.0 + " 秒");
}
private static int[] prepareData(int len) {
Random random = new Random(System.currentTimeMillis());
int[] a = new int[len];
for (int i = 0; i < len; i++) a[i] = random.nextInt(10000);
return a;
}
// 普通排序
private static long normalSort(int[] a) {
long t1 = System.currentTimeMillis();
normalSort(a, 0, a.length - 1);
long t2 = System.currentTimeMillis();
// 检查是否排序成功
for (int i = 1; i < a.length; i++) {
if (a[i] < a[i - 1]) System.out.println("error sort 2");
}
return t2 - t1;
}
private static void normalSort(int[] a, int start, int end) {
if (end <= start) return;
if (end - start == 1 && a[end] < a[start]) {
int k = a[end];
a[end] = a[start];
a[start] = k;
return;
}
int middle = (start + end) / 2;
normalSort(a, start, middle);
normalSort(a, middle + 1, end);
// 合并
merge(a, start, end, middle);
}
// 多线程排序
private static long multiThreadSort(int[] a) {
SortTask task = new SortTask(a, 0, a.length - 1);
long t1 = System.currentTimeMillis();
pool.invoke(task);
long t2 = System.currentTimeMillis();
// 检查是否排序成功
for (int i = 1; i < a.length; i++) {
if (a[i] < a[i - 1]) System.out.println("error sort 1");
}
return t2 - t1;
}
/**
* fork-join 框架实现归并排序
* 这里是分割
*/
private static class SortTask extends RecursiveTask<int[]> {
private int[] val;
private int start;
private int end;
private int middle;
public SortTask(int[] a, int start, int end) {
val = a;
this.start = start;
this.end = end;
middle = (start + end) / 2;
if (merge == null) merge = new int[a.length];
}
@Override
protected int[] compute() {
List<SortTask> moreActions = getMoreActions();
if (moreActions != null && moreActions.size() > 0) {
// 执行所有子线程
for (SortTask t : moreActions) t.fork();
// 等待所有子线程完成
for (SortTask t : moreActions) t.join();
// 合并
merge(val, start, end, middle);
} else {
if (end - start == 1 && val[start] > val[end]) swap(start, end);
}
return val;
}
// 获取需要分割的其他桶任务
private List<SortTask> getMoreActions() {
if (end - start <= 1) return null;
List<SortTask> moreActions = new ArrayList<>();
moreActions.add(new SortTask(val, start, middle));
moreActions.add(new SortTask(val, middle + 1, end));
return moreActions;
}
private void swap(int i, int j) {
int a = val[i];
val[i] = val[j];
val[j] = a;
}
}
// 合并，二分
private static void merge(int[] val, int start, int end, int middle) {
int p1 = start;
int p2 = middle + 1;
int p = start;
while (p1 <= middle || p2 <= end) {
if (p1 > middle) merge[p++] = val[p2++];
else if (p2 > end) merge[p++] = val[p1++];
else if (val[p1] > val[p2]) merge[p++] = val[p2++];
else merge[p++] = val[p1++];
}
for (int i = start; i <= end; i++) val[i] = merge[i];
}
}
我们分别进行100万个数字排序，对各个算法都进行200次排序，可以看到，输出结果：
正常排序共耗时：35.43 秒
多线程排序共耗时：23.898 秒
多线程的排序时间是明显少于单线程的。
但是如果我们把排序次数改为5次：
正常排序共耗时：1.616 秒
多线程排序共耗时：2.905 秒
可以看到，在少量作业的情况下，多线程会带来一些额外的开销，比如线程创建等。
