我有合并排序的示例实现，一个使用 Fork-Join，另一个是直接递归函数。
看起来 fork-join 比直接递归慢，为什么？
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
class DivideTask extends RecursiveTask<int[]> {
private static final long serialVersionUID = -7017440434091885703L;
int[] arrayToDivide;
public DivideTask(int[] arrayToDivide) {
this.arrayToDivide = arrayToDivide;
}
@Override
protected int[] compute() {
//List<RecursiveTask> forkedTasks = new ArrayList<>();
/*
* We divide the array till it has only 1 element.
* We can also custom define this value to say some
* 5 elements. In which case the return would be
* Arrays.sort(arrayToDivide) instead.
*/
if (arrayToDivide.length > 1) {
List<int[]> partitionedArray = partitionArray();
DivideTask task1 = new DivideTask(partitionedArray.get(0));
DivideTask task2 = new DivideTask(partitionedArray.get(1));
invokeAll(task1, task2);
//Wait for results from both the tasks
int[] array1 = task1.join();
int[] array2 = task2.join();
//Initialize a merged array
int[] mergedArray = new int[array1.length + array2.length];
mergeArrays(task1.join(), task2.join(), mergedArray);
return mergedArray;
}
return arrayToDivide;
}
private void mergeArrays(int[] array1, int[] array2, int[] mergedArray) {
int i = 0, j = 0, k = 0;
while ((i < array1.length) && (j < array2.length)) {
if (array1[i] < array2[j]) {
mergedArray[k] = array1[i++];
} else {
mergedArray[k] = array2[j++];
}
k++;
}
if (i == array1.length) {
for (int a = j; a < array2.length; a++) {
mergedArray[k++] = array2[a];
}
} else {
for (int a = i; a < array1.length; a++) {
mergedArray[k++] = array1[a];
}
}
}
private List<int[]> partitionArray() {
int[] partition1 = Arrays.copyOfRange(arrayToDivide, 0, arrayToDivide.length / 2);
int[] partition2 = Arrays.copyOfRange(arrayToDivide, arrayToDivide.length / 2, arrayToDivide.length);
return Arrays.asList(partition1, partition2);
}
}
public class ForkJoinTest {
static int[] numbers;
static final int SIZE = 1_000_000;
static final int MAX = 20;
public static void main(String[] args) {
setUp();
testMergeSortByFJ();
testMergeSort();
}
static void setUp() {
numbers = new int[SIZE];
Random generator = new Random();
for (int i = 0; i < numbers.length; i++) {
numbers[i] = generator.nextInt(MAX);
}
}
static void testMergeSort() {
long startTime = System.currentTimeMillis();
Mergesort sorter = new Mergesort();
sorter.sort(numbers);
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("Mergesort Time:" + elapsedTime + " msec");
}
static void testMergeSortByFJ() {
//System.out.println("Unsorted array: " + Arrays.toString(numbers));
long t1 = System.currentTimeMillis();
DivideTask task = new DivideTask(numbers);
ForkJoinPool forkJoinPool = new ForkJoinPool();
forkJoinPool.invoke(task);
//System.out.println("Sorted array: " + Arrays.toString(task.join()));
System.out.println("Fork-Join Time:" + (System.currentTimeMillis() - t1) + " msec");
}
}
class Mergesort {
private int[] msNumbers;
private int[] helper;
private int number;
private void merge(int low, int middle, int high) {
// Copy both parts into the helper array
for (int i = low; i <= high; i++) {
helper[i] = msNumbers[i];
}
int i = low;
int j = middle + 1;
int k = low;
// Copy the smallest values from either the left or the right side back
// to the original array
while (i <= middle && j <= high) {
if (helper[i] <= helper[j]) {
msNumbers[k] = helper[i];
i++;
} else {
msNumbers[k] = helper[j];
j++;
}
k++;
}
// Copy the rest of the left side of the array into the target array
while (i <= middle) {
msNumbers[k] = helper[i];
k++;
i++;
}
}
private void mergesort(int low, int high) {
// Check if low is smaller then high, if not then the array is sorted
if (low < high) {
// Get the index of the element which is in the middle
int middle = low + (high - low) / 2;
// Sort the left side of the array
mergesort(low, middle);
// Sort the right side of the array
mergesort(middle + 1, high);
// Combine them both
merge(low, middle, high);
}
}
public void sort(int[] values) {
this.msNumbers = values;
number = values.length;
this.helper = new int[number];
mergesort(0, number - 1);
}
}