java并发编程——Fork-Join并行执行任务框架应用

爱被打了一巴掌 2022-12-11 09:23 168阅读 0赞

# Fork-Join并行执行任务框架应用 #

[java并发编程——Fork-Join并行执行任务框架原理][java_Fork-Join]  
[java并发编程——Fork-Join并行执行任务框架应用][java_Fork-Join 1]

## 例子1 ##

我们都知道，快排有2个步骤：  
第1步，拿数组的第1个元素，把元素划分成2半，左边的比该元素小，右边的比该元素大；  
第2步，对左右的2个子数组，分别排序。

可以看出，这里左右2个子数组，可以相互独立的，并行计算。因此可以利用ForkJoin框架， 代码如下：

//定义一个Task，基础自RecursiveAction，实现其compute方法
    class SortTask extends RecursiveAction { 
        final long[] array;
        final int lo;
        final int hi;
        private int THRESHOLD = 0; //For demo only
     
        public SortTask(long[] array) { 
            this.array = array;
            this.lo = 0;
            this.hi = array.length - 1;
        }
     
        public SortTask(long[] array, int lo, int hi) { 
            this.array = array;
            this.lo = lo;
            this.hi = hi;
        }
     
        protected void compute() { 
            if (hi - lo < THRESHOLD)
                sequentiallySort(array, lo, hi);
            else { 
                int pivot = partition(array, lo, hi);  //划分
                coInvoke(new SortTask(array, lo, pivot - 1), new SortTask(array,
                        pivot + 1, hi));  //递归调，左右2个子数组
            }
        }
     
        private int partition(long[] array, int lo, int hi) { 
            long x = array[hi];
            int i = lo - 1;
            for (int j = lo; j < hi; j++) { 
                if (array[j] <= x) { 
                    i++;
                    swap(array, i, j);
                }
            }
            swap(array, i + 1, hi);
            return i + 1;
        }
     
        private void swap(long[] array, int i, int j) { 
            if (i != j) { 
                long temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
     
        private void sequentiallySort(long[] array, int lo, int hi) { 
            Arrays.sort(array, lo, hi + 1);
        }
    }
     
     
    //测试函数
        public void testSort() throws Exception { 
            ForkJoinTask sort = new SortTask(array);   //1个任务
            ForkJoinPool fjpool = new ForkJoinPool();  //1个ForkJoinPool
            fjpool.submit(sort); //提交任务
            fjpool.shutdown(); //结束。ForkJoinPool内部会开多个线程，并行上面的子任务
     
            fjpool.awaitTermination(30, TimeUnit.SECONDS);
        }

## 例子2： 求1到n个数的和 ##

//定义一个Task，基础自RecursiveTask，实现其commpute方法
    public class SumTask extends RecursiveTask<Long>{   
        private static final int THRESHOLD = 10;  
     
        private long start;  
        private long end;  
     
        public SumTask(long n) {   
            this(1,n);  
        }  
     
        private SumTask(long start, long end) {   
            this.start = start;  
            this.end = end;  
        }  
     
        @Override  //有返回值
        protected Long compute() {   
            long sum = 0;  
            if((end - start) <= THRESHOLD){   
                for(long l = start; l <= end; l++){   
                    sum += l;  
                }  
            }else{   
                long mid = (start + end) >>> 1;  
                SumTask left = new SumTask(start, mid);   //分治，递归
                SumTask right = new SumTask(mid + 1, end);  
                left.fork();  
                right.fork();  
                sum = left.join() + right.join();  
            }  
            return sum;  
        }  
        private static final long serialVersionUID = 1L;  
    }  
     
    //测试函数
        public void testSum() throws Exception { 
            SumTask sum = new SumTask(100);   //1个任务
            ForkJoinPool fjpool = new ForkJoinPool();  //1个ForkJoinPool
            Future<Long> future = fjpool.submit(sum); //提交任务
            Long r = future.get(); //获取返回值
            fjpool.shutdown(); 
     
        }

# 参考 #

[Java并发编程指南15：Fork/join并发框架与工作窃取算法剖析][Java_15_Fork_join]

[java_Fork-Join]: https://blog.csdn.net/e891377/article/details/108876370
[java_Fork-Join 1]: https://blog.csdn.net/e891377/article/details/108877162
[Java_15_Fork_join]: https://blog.csdn.net/a724888/article/details/72625224