135-1821-9792

探秘JDK7新特性之fork/join框架

原理解析：fork分解，join结合。这个框架的本质是将一个任务分解成多个子任务，每个子任务用单独的线程去处理。这里用到了递归的思想。框架的结构图可以参考

为巴彦淖尔等地区用户提供了全套网页设计制作服务，及巴彦淖尔网站建设行业解决方案。主营业务为网站建设、成都做网站、巴彦淖尔网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

图片来源(http://www.ibm.com/developerworks/cn/java/j-lo-forkjoin/index.html)

使用fork/join 框架很简单，

1.实现子问题的一般求解算法

2.如何分解问题

3.继承 RecursiveAction ，实现compute()方法

伪代码代码

 
 
 
 
    
  
  
  
  
  1.   Result solve(Problem problem) {     
    2. 
  
  
  
  
  2. if (problem is small)     
    3. 
  
  
  
  
  3.     directly solve problem     
    4. 
  
  
  
  
  4. else {     
    5. 
  
  
  
  
  5.     split problem into independent parts     
    6. 
  
  
  
  
  6.     fork new subtasks to solve each part     
    7. 
  
  
  
  
  7.     join all subtasks     
    8. 
  
  
  
  
  8.     compose result from subresults     
    9. 
  
  
  
  
  9. }   
    10.

 

这里我通过一个改进的二分查找来讲解fork/join的使用。(后面才发现，选用这个案例是非常失败的，因为二分查找的时间是logn,而创建线程的开销更大，这样并不能体现多线程二分查找的优势，所以这个代码不具有实用性，只是为了说明如何使用框架：)

代码如下：

BinarySearchProblem.java

Java代码

 
 
 
 
    
  
  
  
  
  1. package testjdk7;     
    2. 
  
  
  
  
  2.     
    3. 
  
  
  
  
  3. import java.util.Arrays;     
    4. 
  
  
  
  
  4. /**    
    5. 
  
  
  
  
  5.  * @author kencs@foxmail.com    
    6. 
  
  
  
  
  6.  */    
    7. 
  
  
  
  
  7. public class BinarySearchProblem {     
    8. 
  
  
  
  
  8.     private final int[] numbers;     
    9. 
  
  
  
  
  9.     private final int start;     
    10. 
  
  
  
  
  10.     private final int end;     
    11. 
  
  
  
  
  11.     public final int size;     
    12. 
  
  
  
  
  12.          
    13. 
  
  
  
  
  13.     public BinarySearchProblem(int[] numbers,int start,int end){     
    14. 
  
  
  
  
  14.         this.numbers = numbers;     
    15. 
  
  
  
  
  15.         this.start = start;     
    16. 
  
  
  
  
  16.         this.end = end;     
    17. 
  
  
  
  
  17.         this.size = end -start;     
    18. 
  
  
  
  
  18.     }     
    19. 
  
  
  
  
  19.          
    20. 
  
  
  
  
  20.     public int searchSequentially(int numberToSearch){     
    21. 
  
  
  
  
  21.        //偷懒，不自己写二分查找了     
    22. 
  
  
  
  
  22.        return Arrays.binarySearch(numbers, start, end, numberToSearch);     
    23. 
  
  
  
  
  23.     }     
    24. 
  
  
  
  
  24.          
    25. 
  
  
  
  
  25.     public BinarySearchProblem subProblem(int subStart,int subEnd){     
    26. 
  
  
  
  
  26.         return new BinarySearchProblem(numbers,start+subStart,start+subEnd);     
    27. 
  
  
  
  
  27.     }     
    28. 
  
  
  
  
  28. }  
    29.

 

BiSearchWithForkJoin.java

Java代码

 
 
 
 
    
  
  
  
  
  1. package testjdk7;     
    2. 
  
  
  
  
  2. import java.util.concurrent.ForkJoinPool;     
    3. 
  
  
  
  
  3. import java.util.concurrent.RecursiveAction;     
    4. 
  
  
  
  
  4.     
    5. 
  
  
  
  
  5. /**    
    6. 
  
  
  
  
  6.  * @author kencs@foxmail.com    
    7. 
  
  
  
  
  7.  */    
    8. 
  
  
  
  
  8. public class BiSearchWithForkJoin extends RecursiveAction {     
    9. 
  
  
  
  
  9.     private final int threshold;     
    10. 
  
  
  
  
  10.     private final BinarySearchProblem problem;     
    11. 
  
  
  
  
  11.     public int result;     
    12. 
  
  
  
  
  12.     private final int numberToSearch;     
    13. 
  
  
  
  
  13.          
    14. 
  
  
  
  
  14.     public BiSearchWithForkJoin(BinarySearchProblem problem,int threshold,int numberToSearch){     
    15. 
  
  
  
  
  15.         this.problem = problem;     
    16. 
  
  
  
  
  16.         this.threshold = threshold;     
    17. 
  
  
  
  
  17.         this.numberToSearch = numberToSearch;     
    18. 
  
  
  
  
  18.     }     
    19. 
  
  
  
  
  19.     
    20. 
  
  
  
  
  20.     @Override    
    21. 
  
  
  
  
  21.     protected void compute() {     
    22. 
  
  
  
  
  22.        if(problem.size < threshold){ //小于阀值，就直接用普通的二分查找     
    23. 
  
  
  
  
  23.            result = problem.searchSequentially(numberToSearch);     
    24. 
  
  
  
  
  24.        }else{     
    25. 
  
  
  
  
  25.            //分解子任务     
    26. 
  
  
  
  
  26.            int midPoint = problem.size/2;     
    27. 
  
  
  
  
  27.            BiSearchWithForkJoin left = new BiSearchWithForkJoin(problem.subProblem(0, midPoint),threshold,numberToSearch);     
    28. 
  
  
  
  
  28.            BiSearchWithForkJoin right = new BiSearchWithForkJoin(problem.subProblem(midPoint+1, problem.size),threshold,numberToSearch);     
    29. 
  
  
  
  
  29.            invokeAll(left,right);     
    30. 
  
  
  
  
  30.            result = Math.max(left.result, right.result);     
    31. 
  
  
  
  
  31.        }     
    32. 
  
  
  
  
  32.     }     
    33. 
  
  
  
  
  33.          
    34. 
  
  
  
  
  34.     //构造数据     
    35. 
  
  
  
  
  35.     private static final int[] data = new int[1000_0000];     
    36. 
  
  
  
  
  36.     static{     
    37. 
  
  
  
  
  37.         for(int i = 0;i<1000_0000;i++){     
    38. 
  
  
  
  
  38.             data[i] = i;     
    39. 
  
  
  
  
  39.         }     
    40. 
  
  
  
  
  40.     }     
    41. 
  
  
  
  
  41.     public static void main(String[] args){     
    42. 
  
  
  
  
  42.        BinarySearchProblem problem = new BinarySearchProblem(data,0,data.length);     
    43. 
  
  
  
  
  43.        int threshold = 100;     
    44. 
  
  
  
  
  44.        int nThreads = 10;     
    45. 
  
  
  
  
  45.        //查找100_0000所在的下标     
    46. 
  
  
  
  
  46.        BiSearchWithForkJoin  bswfj = new BiSearchWithForkJoin(problem,threshold,100_0000);     
    47. 
  
  
  
  
  47.        ForkJoinPool fjPool = new ForkJoinPool(nThreads);     
    48. 
  
  
  
  
  48.        fjPool.invoke(bswfj);     
    49. 
  
  
  
  
  49.        System.out.printf("Result is:%d%n",bswfj.result);     
    50. 
  
  
  
  
  50.     }     
    51. 
  
  
  
  
  51.          
    52. 
  
  
  
  
  52.          
    53. 
  
  
  
  
  53. }   
    54.

 

RecursiveTask 还可以带返回值，这里给出一段代码作为参考(斐波那契函数)

(来自http://www.ibm.com/developerworks/cn/java/j-lo-forkjoin/index.html)

Java代码

 
 
 
 
    
  
  
  
  
  1. class Fibonacci extends RecursiveTask  {      
    2. 
  
  
  
  
  2.     final int n;     
    3. 
  
  
  
  
  3.     
    4. 
  
  
  
  
  4.     Fibonacci(int n) {     
    5. 
  
  
  
  
  5.         this.n = n;     
    6. 
  
  
  
  
  6.     }     
    7. 
  
  
  
  
  7.     
    8. 
  
  
  
  
  8.     private int compute(int small) {     
    9. 
  
  
  
  
  9.         final int[] results = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 };     
    10. 
  
  
  
  
  10.         return results[small];     
    11. 
  
  
  
  
  11.     }     
    12. 
  
  
  
  
  12.     
    13. 
  
  
  
  
  13.     public Integer compute() {     
    14. 
  
  
  
  
  14.         if (n <= 10) {     
    15. 
  
  
  
  
  15.             return compute(n);     
    16. 
  
  
  
  
  16.         }     
    17. 
  
  
  
  
  17.         Fibonacci f1 = new Fibonacci(n - 1);     
    18. 
  
  
  
  
  18.         Fibonacci f2 = new Fibonacci(n - 2);     
    19. 
  
  
  
  
  19.         System.out.println("fork new thread for " + (n - 1));     
    20. 
  
  
  
  
  20.         f1.fork();     
    21. 
  
  
  
  
  21.         System.out.println("fork new thread for " + (n - 2));     
    22. 
  
  
  
  
  22.         f2.fork();     
    23. 
  
  
  
  
  23.         return f1.join() + f2.join();     
    24. 
  
  
  
  
  24.     }     
    25. 
  
  
  
  
  25. }   
    26.

 

用途

只要问题能够分解成类似子问题的，都可以使用这个框架。对于大批量的数据尤其合适

参考资料

Jdk7官网 http://openjdk.java.net/projects/jdk7/

(注：这篇文章发表时，JDK7未正式公布，可能有误差，具体以官方正式版为准)


网页题目：探秘JDK7新特性之fork/join框架
文章链接：http://www.wtcwzsj.com/article/dhiseci.html

其他资讯


关于我们
我们的服务
网站建设案例
新闻动态
联系我们

135-1821-9792

公司服务热线
友情链接： 400电话办理   njyarui.cn   重庆app软件开发   scyucang.cn   led电子产品   成都画册快印   江油做网站   温江网站建设   月饼包装礼品盒   cdganxi.cn   

Copyright © 2009-2022 www.wtcwzsj.com 青羊区广皓图文设计工作室（个体工商户） 版权所有　蜀ICP备19037934号