Java并发基础实践：分而治之

Java并发基础实践：分而治之2014-08-17 blogjava Sha Jiang本系列的第三篇文章将以实现一个极简单的查找最大数的任务为例，分别给出了四个版本：1.顺序执行；2.基于传统的Thread.join（）；3.基于并发工具包的Future；4.基于JDK 7引入的Fork/Join框架。（2013.10.25最后更新）
分而治之（Divide-and-Conquer）是解决复杂问题的常用方法。在并发应用中，可将一个复杂算法分解为若干子问题，然后使用独立的线程去执行解决子问题的程序，之后再将各个子问题的结果逐级进行合并以得到最终结果。在特定环境中，这种方式可能较好地提高程序的执行效率。方案1：顺序执行找出对给定整形数组中的最大值，使用的方法很简单，就是逐一遍历每个元素，将当前元素与当前最大值进行比较，若当前元素的值更大，则将该值作为新的当前最大值，再去与下一个元素进行比较，如此反复。在编写并发程序来实现这个算法之前，本文将先给出一个顺序执行的实现版本，但依然利用了分而治之的思想。即，先将给定数列分割成若干较小的子数列，找出各个子数列的最大值，将这些最大值组成一个新的数列，然后再使用同样的方法对这个新数列进行分割与最大值合并，...依次类推，直至找到最大值。代码清单1中的MaxNumberFinder是本文的基础类：1.getMaxNumber（）方法展示了如何查找一个数列中的最大值；2.使用工具方法getNumberArray（）/createNumberArray（）可以创建指定长度的随机整数数列；3.方法findMaxNumber（）展示了将一个数列分割为子数列（子数列的最大长度不超过指定值THRESHOLD），并查找子数列的最大值，以及将子数列的最大值组成各级新的中间数列去查找其最大值。

清单1public class MaxNumberFinder {public static final int THRESHOLD = 50;private static final Random random = new Random（）;public static int[] getNumberArray（） {return createNumberArray（3000）;}private static int[] createNumberArray（int capacity） {int[] numbers = new int[capacity];for （int i = 0; i < numbers.length; i++） {numbers[i] = random.nextInt（capacity）;}return numbers;}public static int getMaxNumber（int[] numbers） {if （numbers.length == 0） {return Integer.MIN_VALUE;}int max = numbers[0];for （int i = 1; i < numbers.length; i++） {if （numbers[i] > max） {max = numbers[i];}}return max;}private static int findMaxNumber（int[] numbers） {// interim max number arrayint[] maxNumbers = new int[numbers.length / THRESHOLD + （numbers.length % THRESHOLD == 0 ？ 0 : 1）];for （int i = 0; i <= numbers.length - THRESHOLD; i += THRESHOLD） {final int[] subNumbers = new int[THRESHOLD];System.arraycopy（numbers, i, subNumbers, 0, subNumbers.length）;maxNumbers[i / THRESHOLD] = getMaxNumber（subNumbers）;}if （numbers.length % THRESHOLD ！= 0） {int[] lastSubNumbers = new int[numbers.length % THRESHOLD];System.arraycopy（numbers, numbers.length - lastSubNumbers.length, lastSubNumbers, 0, lastSubNumbers.length）;maxNumbers[maxNumbers.length - 1] = getMaxNumber（lastSubNumbers）;}// if the length of interim max number array is greater than threshold,// it must divide-and-search recursively.if （maxNumbers.length > THRESHOLD） {return findMaxNumber（maxNumbers）;} else {return getMaxNumber（maxNumbers）;}}}