本文為原創(chuàng)文章挽霉，轉(zhuǎn)載請(qǐng)注明出處
查看[Java]系列內(nèi)容請(qǐng)點(diǎn)擊：http://www.reibang.com/nb/45938443
fork-join框架會(huì)使用空閑線程來?yè)屨籍?dāng)前線程的任務(wù)，具體實(shí)現(xiàn)原理這里就不說了屁擅，有興趣的同學(xué)也可以自己實(shí)現(xiàn)一個(gè)缅帘。這里使用該框架進(jìn)行歸并排序衰粹，并對(duì)比普通的歸并排序的效率：
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萬個(gè)數(shù)字排序
int sortTimes = 200; // 排序次數(shù)
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("正常排序共耗時(shí)：" + (t2 - t1) / 1000.0 + " 秒");
// 多線程排序
t1 = System.currentTimeMillis();
for (int t = 0; t < sortTimes; t++) {
multiThreadSort(prepareData(len));
}
t2 = System.currentTimeMillis();
System.out.println("多線程排序共耗時(shí)：" + (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 框架實(shí)現(xiàn)歸并排序
* 這里是分割
*/
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) {
// 執(zhí)行所有子線程
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;
}
// 獲取需要分割的其他桶任務(wù)
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];
}
}
我們分別進(jìn)行100萬個(gè)數(shù)字排序，對(duì)各個(gè)算法都進(jìn)行200次排序憋活，可以看到岂津，輸出結(jié)果：
正常排序共耗時(shí)：35.43 秒
多線程排序共耗時(shí)：23.898 秒
多線程的排序時(shí)間是明顯少于單線程的。
但是如果我們把排序次數(shù)改為5次：
正常排序共耗時(shí)：1.616 秒
多線程排序共耗時(shí)：2.905 秒
可以看到悦即，在少量作業(yè)的情況下吮成，多線程會(huì)帶來一些額外的開銷，比如線程創(chuàng)建等辜梳。
