本文主要是介绍用ForkJoin框架为归并排序提速，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
归并排序典型的分治思想的算法。每层递归有三个步骤
- 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
- 解决（Conquer）：用合并排序法对两个子序列递归的排序。
- 合并（Combine）：合并两个已排序的子序列已得到排序结果。
使用递归算法的代码demo
public class SortArray {int[] tmp;public int[] sortArray(int[] nums) {tmp = new int[nums.length];mergeSort(nums, 0, nums.length - 1);return nums;}private void mergeSort(int[] nums, int left, int right) {if (left >= right) {return;}int middle = (left + right) / 2;mergeSort(nums, left, middle);int newLeft = middle + 1;mergeSort(nums, newLeft, right);int i = left, j = newLeft;int k = 0;while (i <= middle && j <= right) {if (nums[i] < nums[j]) {tmp[k++] = nums[i++];} else {tmp[k++] = nums[j++];}}while (i <= middle) {tmp[k++] = nums[i++];}while (j <= right) {tmp[k++] = nums[j++];}for (i = 0; i < k; i++) {nums[left + i] = tmp[i];}}public static void main(String[] args) {SortArray test = new SortArray();int[] array = test.sortArray(new int[]{5, 2, 3, 1});System.out.println(Arrays.toString(array));array = test.sortArray(new int[]{5, 1, 1, 2, 0, 0});System.out.println(Arrays.toString(array));}
}
写完之后，想到这个程序仅仅利用到了一个cpu核心，如果数据量很大的情况下，会造成计算资源的浪费。这个需要计算多个子任务的分治算法，明显可以用Fork/Join框架提速。于是改写了一版。当数据量小于1024个的时候不再进行切割，否则任务太多，提速效果十分差。当小于1024个的时候，偷懒用了工具库的快排。源码地址：https://github.com/bruce256/LeetCodeOJ/blob/master/src/main/java/divideAndConquer/SortArrayTask.java
public class SortArrayTask extends RecursiveTask<int[]> {public static final int THRESHOLD = 1024;int[] nums;int left;int right;int[] tmp;public SortArrayTask(int[] nums, int[] tmp, int left, int right) {this.nums = nums;this.left = left;this.right = right;this.tmp = tmp;}@Overrideprotected int[] compute() {if (right - left + 1 <= THRESHOLD) {Arrays.sort(nums, left, right + 1);return null;}int middle = (left + right) / 2;// 当前任务纳入计算队列SortArrayTask leftSortArrayTask = new SortArrayTask(nums, tmp, left, middle);leftSortArrayTask.fork();int newLeft = middle + 1;SortArrayTask rightSortArrayTask = new SortArrayTask(nums, tmp, newLeft, right);rightSortArrayTask.fork();// 等待任务计算结束，再做这个语句后的事情leftSortArrayTask.join();rightSortArrayTask.join();int i = left, j = newLeft;int k = 0;while (i <= middle && j <= right) {if (nums[i] < nums[j]) {tmp[k++] = nums[i++];} else {tmp[k++] = nums[j++];}}while (i <= middle) {tmp[k++] = nums[i++];}while (j <= right) {tmp[k++] = nums[j++];}for (i = 0; i < k; i++) {nums[left + i] = tmp[i];}return nums;}public static void main(String[] args) {int[] array = {10000, 100000, 1000000, 10000000, 100000000};for (int num : array) {compare(num);}}private static void compare(int num) {int[] nums = new int[num];int[] tmp = new int[num];Random random = new Random();for (int i = 0; i < nums.length; i++) {nums[i] = random.nextInt();}System.out.println(nums.length + " numbers \t" + Runtime.getRuntime().availableProcessors() + " cpus");ForkJoinPool forkJoinPool = new ForkJoinPool();SortArrayTask task = new SortArrayTask(nums, tmp, 0, nums.length - 1);long start = System.currentTimeMillis();Future<int[]> result = forkJoinPool.submit(task);try {int[] r = result.get();long duration = System.currentTimeMillis() - start;System.out.println("fork/join time cost: \t" + duration + " ms");} catch (InterruptedException e) {e.printStackTrace();} catch (ExecutionException e) {e.printStackTrace();}SortArray test = new SortArray();for (int i = 0; i < nums.length; i++) {nums[i] = random.nextInt();}start = System.currentTimeMillis();int[] array = test.sortArray(nums);long duration = System.currentTimeMillis() - start;System.out.println("single thread time cost: \t" + duration + " ms");}
}
我的电脑是i7 4核心8线程，跑了10000, 100000, 1000000, 10000000, 100000000个数据对别单线程和多线程版本，运行结果
10000 numbers 8 cpus
fork/join time cost: 5 ms
single thread time cost: 4 ms100000 numbers 8 cpus
fork/join time cost: 29 ms
single thread time cost: 29 ms1000000 numbers 8 cpus
fork/join time cost: 80 ms
single thread time cost: 142 ms10000000 numbers 8 cpus
fork/join time cost: 235 ms
single thread time cost: 1725 ms100000000 numbers 8 cpus
fork/join time cost: 2284 ms
single thread time cost: 17275 ms当数据量较小时，由于CPU上下文切换，导致并行还不如串行快。当数据量较大时，提速明显。
这篇关于用ForkJoin框架为归并排序提速的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
