精华内容
下载资源
问答
  • 2022-04-19 21:21:29

    L2-025 分而治之 (25 分)

    分而治之,各个击破是兵家常用的策略之一。在战争中,我们希望首先攻下敌方的部分城市,使其剩余的城市变成孤立无援,然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序,判断每个方案的可行性。

    输入格式:

    输入在第一行给出两个正整数 N 和 M(均不超过10 000),分别为敌方城市个数(于是默认城市从 1 到 N 编号)和连接两城市的通路条数。随后 M 行,每行给出一条通路所连接的两个城市的编号,其间以一个空格分隔。在城市信息之后给出参谋部的系列方案,即一个正整数 K (≤ 100)和随后的 K 行方案,每行按以下格式给出:

    Np v[1] v[2] ... v[Np]
    

    其中 Np 是该方案中计划攻下的城市数量,后面的系列 v[i] 是计划攻下的城市编号。

    输出格式:

    对每一套方案,如果可行就输出YES,否则输出NO

    输入样例:

    10 11
    8 7
    6 8
    4 5
    8 4
    8 1
    1 2
    1 4
    9 8
    9 1
    1 10
    2 4
    5
    4 10 3 8 4
    6 6 1 7 5 4 9
    3 1 8 4
    2 2 8
    7 9 8 7 6 5 4 2
    

    输出样例:

    NO
    YES
    YES
    NO
    NO

    本题思路

    本题思路其实比较简单,创建一个邻接链表(邻接矩阵会爆内存,Java咋样都会爆(可以使用特殊读入可过))然后我们记录每一次删除的节点,然后就遍历邻接链表,如果出现不满足的就退出,输出NO即可,否则输出YES,主要本题难点,会发生内存超限的情况,本题应该也可以通过并查集来解,但是博主没有尝试.

    下面上代码

    Java(邻接矩阵,链表都会内存超限)

    需要使用StreamTokenizer读入可通过

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.PrintWriter;
    import java.io.StreamTokenizer;
    import java.util.ArrayList;
    import java.util.List;
    
    public class Main分而治之 {
    	public static void main(String[] args) throws IOException {
    		StreamTokenizer x=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    		PrintWriter out=new PrintWriter(System.out);
    		x.nextToken();
    		int n=(int)x.nval;
    		x.nextToken();
    		int m=(int)x.nval;
    		List<Integer> aa[]=new ArrayList[n+1];
    		boolean bj[]=new boolean[n+1];
    		while(m--!=0){
    			x.nextToken();
    			int i=(int)x.nval;
    			int j=(int)x.nval;
    			if(aa[i]==null)
    				aa[i]=new ArrayList<Integer>();
    			if(aa[j]==null)
    				aa[j]=new ArrayList<Integer>();
    			aa[i].add(j);
    			aa[j].add(i);
    		}
    		x.nextToken();
    		int k=(int)x.nval;
    		while(k--!=0) {
    			boolean f=true;
    			x.nextToken();
    			int w=(int)x.nval;
    			for(int i=1;i<=n;i++) {bj[i]=false;}
    			for(int i=1;i<=w;i++) {
    				x.nextToken();
    				bj[(int)x.nval]=true;
    			}
    			for(int i=1;i<=n&&f;i++) {
    				if(!bj[i]&&aa[i]!=null) {
    					for(int j=0;j<aa[i].size();j++) {
    						if(!bj[aa[i].get(j)]) {
    							f=false;
    							break;
    						}
    					}
    				}
    			}
    			if(f)
    				System.out.println("YES");
    			else
    				System.out.println("NO");
    		}
    	}
    }
    

     c++(邻接矩阵会爆,链表不会爆)

    #include <bits/stdc++.h>
    using namespace std;
    
    int main(){
    		int n;
    		int m;
    		scanf("%d %d",&n,&m);
    		vector<int> aa[10010];
    		while(m--!=0) {
    			int i,j;
    			scanf("%d %d",&i,&j);
    			aa[i-1].push_back(j-1);
    			aa[j-1].push_back(i-1);
    		}
    		scanf("%d",&m);
    		int f[10010];
    		while(m--!=0) {
    			int flag=1;
    			int k;
    			scanf("%d",&k);
    			for(int i=0;i<n;i++){
    				f[i]=1;
    			}
    			while(k--!=0) {
    				int i;
    				scanf("%d",&i);
    				f[i-1]=0;
    			}
    			for(int i=0;i<n&&flag;i++) {
    				for(int j=0;j<aa[i].size();j++) {
    					if(f[i]==1&&f[aa[i][j]]==1) {
    						flag=0;
    						break;
    					}
    				}
    			}
    			if(flag)
    				cout<<"YES"<<endl;
    			else
    				cout<<"NO"<<endl;
    		}
    
    }
    

    更多相关内容
  • L2-025 分而治之

    2021-01-03 23:01:28
    L2-025 分而治之 这是一道简单题,写着篇博客主要是给自己提个醒,做题要学会变通 这道题我一直在考虑如何对点进行操作,结果超时,但实际上这题对边进行遍历一遍就好了 #include using namespace std; vectorv...
  • 在 MatLab 中应用分治法的简单方法 输入:X => 要排序的向量输出: sorted_x => 排序后的 X 从小值到最大值sorted_loc => 旧 X 中已排序数据的位置
  • 1.分而治之的概念   分而治之是一种使用递归解决问题的算法,主要的技巧是将一个大的复杂的问题划分为多个子问题,而这些子问题可以作为终止条件,或者在一个递归步骤中得到解决,所有子问题的解决结合起来就构成...
  • 分而治之Delaunay三角剖分器 程式码范例 var model = new Mesh ( ) ; model . delaunay ( ) ; 约束Delaunay三角剖分 在制品 网格细化 在制品 已知错误 无法处理三角剖分中的重复点; 递归缓慢; 去做 完善SVG的...
  • 分而治之

    2021-03-31 11:17:23
    分而治之 L2-025 分而治之 (25 分) 分而治之,各个击破是兵家常用的策略之一。在战争中,我们希望首先攻下敌方的部分城市,使其剩余的城市变成孤立无援,然后再分头各个击破。为此参谋部提供了若干打击方案。本题就...

    分而治之

    L2-025 分而治之 (25 分)
    分而治之,各个击破是兵家常用的策略之一。在战争中,我们希望首先攻下敌方的部分城市,使其剩余的城市变成孤立无援,然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序,判断每个方案的可行性。

    输入格式
    输入在第一行给出两个正整数 N 和 M(均不超过10 000),分别为敌方城市个数(于是默认城市从 1 到 N 编号)和连接两城市的通路条数。随后 M 行,每行给出一条通路所连接的两个城市的编号,其间以一个空格分隔。在城市信息之后给出参谋部的系列方案,即一个正整数 K (≤ 100)和随后的 K 行方案,每行按以下格式给出:

    Np v[1] v[2] … v[Np]
    其中 Np 是该方案中计划攻下的城市数量,后面的系列 v[i] 是计划攻下的城市编号。

    输出格式:
    对每一套方案,如果可行就输出YES,否则输出NO。

    输入样例:

    10 11
    8 7
    6 8
    4 5
    8 4
    8 1
    1 2
    1 4
    9 8
    9 1
    1 10
    2 4
    5
    4 10 3 8 4
    6 6 1 7 5 4 9
    3 1 8 4
    2 2 8
    7 9 8 7 6 5 4 2
    

    输出样例:

    NO
    YES
    YES
    NO
    NO
    

    题解天梯赛拿了0分的题,nc的用了并查集。
    这题就是遍历一个邻接表。每一个城市会有一些援军,那么这些援军就是他们的出口,如果把所有出口堵上就是孤立无援状态。出口就是每个节点的出度,读入边的时候把每个点的出度记录下来,被攻占的城市就把与他相连的节点的出度减1,全部攻占之后就看是不是所有的城市出度<=0即可。

    #include <iostream>
    #include<algorithm>
    #include<cstring>
    const int N=20010;
    int h[N],e[N],idx,ne[N];
    int d1[N],d2[N];
    int n,m,k;
    using namespace std;
    void add(int a,int b)
    {
    	ne[idx]=h[a],e[idx]=b,h[a]=idx++;
    }
    void attack(int y)
    {   d2[y]=0;
    	for(int i=h[y];i!=-1;i=ne[i])
    	{
    		int j=e[i];
    		d2[j]--;
    	}
    }
    int main()
    {  memset(h,-1,sizeof h);
       scanf("%d%d",&n,&m);
       while(m--)
       {
       	 int a,b;
       	 scanf("%d%d",&a,&b);
       	 add(a,b),add(b,a);
    	 d1[a]++,d1[b]++; 
       }
       scanf("%d",&k);
       while(k--)
       { memcpy(d2,d1,sizeof(d1));
       	int x;
       	scanf("%d",&x);
       	while(x--)
       	{   int y;
       	    scanf("%d",&y);
       		attack(y);	
    	}
    	int flag=0;
    	for(int i=1;i<=n;i++)
    	{
    		if(d2[i]>0) 
    		{
    			printf("NO\n");
    			flag=1;
    			break;
    		 } 
    	}
    	if(flag==0)
    	printf("YES\n");
       }
    }
    
    展开全文
  • 分而治之的思想解决求一个数组的最大子集,有效的降低了时间复杂度,值得学习。
  • 大整数相乘问题利用分而治之算法--来源于平时的作业
  • 使用分而治之策略进行图像增强
  • 该项目开发了新的新技术和算法,可以使用“树状图”的“分而治之”方法在各种任意形状和空间内快速划分和可视化非常大的层次结构。 相关出版物:...
  • 采用分而治之策略的基于增量密度的聚类:3DC聚类
  • 通过二分法,逐次缩小问题范围,在查找问题时,这个方法是唯一需要应用的规则,所有其它规则都是帮助你遵循这条规则。
  • 分而治之算法 什么是分而治之算法? (不,这不是“分而治之”) (What are Divide and Conquer Algorithms? (And no, it's not "Divide and Concur")) Divide and Conquer is an algorithmic paradigm (sometimes ...

    分而治之算法

    什么是分而治之算法? (不,这不是“分而治之”) (What are Divide and Conquer Algorithms? (And no, it's not "Divide and Concur"))

    Divide and Conquer is an algorithmic paradigm (sometimes mistakenly called "Divide and Concur" - a funny and apt name), similar to Greedy and Dynamic Programming. A typical Divide and Conquer algorithm solves a problem using the following three steps.

    “分而治之”是一种算法范式(有时被错误地称为“ Divide and Concur”(一个有趣且恰当的名称)),类似于“贪婪和动态编程”。 典型的分而治之算法使用以下三个步骤来解决问题。

    1. Divide: Break the given problem into subproblems of same type. This step involves breaking the problem into smaller sub-problems. Sub-problems should represent a part of the original problem. This step generally takes a recursive approach to divide the problem until no sub-problem is further divisible. At this stage, sub-problems become atomic in nature but still represent some part of the actual problem.

      划分 :将给定问题分解为相同类型的子问题。 此步骤涉及将问题分解为较小的子问题。 子问题应该代表原始问题的一部分。 此步骤通常采用递归方法来划分问题,直到没有子问题可以进一步分割为止。 在这个阶段,子问题本质上已成为原子问题,但仍代表实际问题的一部分。

    2. Conquer: Recursively solve these sub-problems. This step receives a lot of smaller sub-problems to be solved. Generally, at this level, the problems are considered 'solved' on their own.

      征服 :递归解决这些子问题。 此步骤收到许多要解决的较小子问题。 通常,在此级别上,问题被认为是“已解决”。

    3. Combine: Appropriately combine the answers. When the smaller sub-problems are solved, this stage recursively combines them until they formulate a solution of the original problem. This algorithmic approach works recursively and conquer & merge steps works so close that they appear as one.

      合并 :适当合并答案。 解决了较小的子问题后,此阶段将它们递归组合,直到它们为原始问题制定了解决方案。 这种算法方法递归地起作用,征服和合并步骤如此接近以至于它们看起来像一个。

    This method usually allows us to reduce the time complexity by a large extent.

    这种方法通常可以使我们在很大程度上减少时间复杂度。

    For example, Bubble Sort uses a complexity of O(n^2), whereas quicksort (an application Of Divide And Conquer) reduces the time complexity to O(nlog(n)). Linear Search has time complexity O(n), whereas Binary Search (an application Of Divide And Conquer) reduces time complexity to O(log(n)).

    例如,冒泡排序使用O(n^2)的复杂度,而快速排序(分而治之的应用程序)将时间复杂度降低为O(nlog(n)) 。 线性搜索的时间复杂度为O(n) ,而二进制搜索(分而治之的应用)将时间复杂度降低为O(log(n))

    Following are some standard algorithms that are of the Divide and Conquer algorithms variety.

    以下是分而治之算法的一些标准算法。

    Binary Search  is a searching algorithm. In each step, the algorithm compares the input element (x) with the value of the middle element in array. If the values match, return the index of middle. Otherwise, if x is less than the middle element, then the algorithm recurs to the left side of the middle element, else it recurs to the right side of the middle element.

    二进制搜索是一种搜索算法。 在每个步骤中,算法都会将输入元素(x)与数组中中间元素的值进行比较。 如果值匹配,则返回中间索引。 否则,如果x小于中间元素,则算法递归到中间元素的左侧,否则算法递归到中间元素的右侧。

    Quicksort  is a sorting algorithm. The algorithm picks a pivot element, rearranges the array elements in such a way that all elements smaller than the picked pivot element move to the left side of the pivot, and all greater elements move to the right side. Finally, the algorithm recursively sorts the subarrays on left and right of pivot element.

    Quicksort是一种排序算法。 该算法选择一个枢轴元素,以这样一种方式重新排列数组元素:所有小于所拾取枢轴元素的元素都移到枢轴的左侧,所有更大的元素都移到右侧。 最后,该算法对枢轴元素左右两侧的子数组进行递归排序。

    Merge Sort  is also a sorting algorithm. The algorithm divides the array into two halves, recursively sorts them, and finally merges the two sorted halves. The time complexity of this algorithm is O(nLogn), be it best case, average case or worst case. It's time complexity can be easily understood from the recurrence equates to: T(n) = 2T(n/2) + n.

    合并排序也是一种排序算法。 该算法将数组分为两个半部分,对它们进行递归排序,最后合并两个排序的半部分。 该算法的时间复杂度为O(nLogn) ,无论是最佳情况,平均情况还是最坏情况。 从时间等于T(n) = 2T(n/2) + n可以很容易地理解它的时间复杂度。

    Closest Pair of Points  The problem is to find the closest pair of points in a set of points in x-y plane. The problem can be solved in O(n^2) time by calculating distances of every pair of points and comparing the distances to find the minimum. The Divide and Conquer algorithm solves the problem in O(nLogn) time.

    最接近的点对问题是在xy平面中的一组点中找到最接近的点对。 通过计算每对点的距离并比较距离以找出最小值,可以在O(n^2)时间内解决该问题。 分而治之算法解决了O(nLogn)时间的问题。

    Strassen’s Algorithm  is an efficient algorithm to multiply two matrices. A simple method to multiply two matrices need 3 nested loops and is O(n^3). Strassen’s algorithm multiplies two matrices in O(n^2.8974) time.

    Strassen算法是将两个矩阵相乘的高效算法。 一个简单的将两个矩阵相乘的方法需要3个嵌套循环,并且为O(n^3) 。 Strassen算法在O(n^2.8974)时间内将两个矩阵相乘。

    Cooley–Tukey Fast Fourier Transform (FFT) algorithm  is the most common algorithm for FFT. It is a divide and conquer algorithm which works in O(nlogn) time.

    Cooley–Tukey快速傅立叶变换(FFT)算法FFT最常用的算法。 这是一种分治法,可在O(nlogn)时间内使用。

    The Karatsuba algorithm  was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. It reduces the multiplication of two n-digit numbers to at most to n^1.585 (which is approximation of log of 3 in base 2) single digit products. It is therefore faster than the classical algorithm, which requires n^2 single-digit products.

    Karatsuba算法是第一个渐进地快于二次“等级学校”算法的乘法算法。 它将两个n位数字的乘积最多减少到n ^ 1.585(以2为底的对数3的对数)。 因此,它比经典算法快,后者需要n ^ 2个单位的乘积。

    分而治之(D&C)与动态编程(DP) (Divide and Conquer (D & C) vs Dynamic Programming (DP))

    Both paradigms (D & C and DP) divide the given problem into subproblems and solve subproblems. How to choose one of them for a given problem? Divide and Conquer should be used when same subproblems are not evaluated many times. Otherwise Dynamic Programming or Memoization should be used.

    两种范例(D&C和DP)都将给定的问题分为子问题并解决子问题。 如何为给定问题选择其中之一? 当相同子问题没有被多次评估时,应使用分而治之。 否则,应使用动态编程或记忆。

    For example, Binary Search is a Divide and Conquer algorithm, we never evaluate the same subproblems again. On the other hand, for calculating the nth Fibonacci number, Dynamic Programming should be preferred.

    例如,二进制搜索是一种分而治之的算法,我们再也不会评估相同的子问题。 另一方面,为了计算第n个斐波那契数,应首选动态编程。

    翻译自: https://www.freecodecamp.org/news/divide-and-conquer-algorithms/

    分而治之算法

    展开全文
  • 学习分而治之(divide and conquer,D&C 递归式问题解决方案)。分而治之是学习的第一种通用解决方法。 学习快速排序法——一种优雅的排序算法。比第二章介绍的选择排序快的多。使用的是分而治之的策略。 目录 ...
  • 分而治之的风格。 Intellij IDEA社区版14.1.5项目 一个任务 Минимальное расстояние Дан набор из N точек на плоскости (для простоты можно с...
  • 写在前面在JDK中,提供了这样一种功能:它能够将复杂的逻辑拆分成一个个简单的逻辑来并行执行,待每个并行执行的逻辑执行完成后,再将...分而治之就是将一个复杂的计算,按照设定的阈值分解成多个计算,然后将各个计...

    写在前面

    在JDK中,提供了这样一种功能:它能够将复杂的逻辑拆分成一个个简单的逻辑来并行执行,待每个并行执行的逻辑执行完成后,再将各个结果进行汇总,得出最终的结果数据。有点像Hadoop中的MapReduce。

    ForkJoin是由JDK1.7之后提供的多线程并发处理框架。ForkJoin框架的基本思想是分而治之。什么是分而治之?分而治之就是将一个复杂的计算,按照设定的阈值分解成多个计算,然后将各个计算结果进行汇总。相应的,ForkJoin将复杂的计算当做一个任务,而分解的多个计算则是当做一个个子任务来并行执行。

    Java并发编程的发展

    对于Java语言来说,生来就支持多线程并发编程,在并发编程领域也是在不断发展的。Java在其发展过程中对并发编程的支持越来越完善也正好印证了这一点。

    Java 1 支持thread,synchronized。

    Java 5 引入了 thread pools, blocking queues, concurrent collections,locks, condition queues。

    Java 7 加入了fork-join库。

    Java 8 加入了 parallel streams。

    并发与并行

    并发和并行在本质上还是有所区别的。

    并发

    并发指的是在同一时刻,只有一个线程能够获取到CPU执行任务,而多个线程被快速的轮换执行,这就使得在宏观上具有多个线程同时执行的效果,并发不是真正的同时执行,并发可以使用下图表示。

    da66efe882f3

    image

    并行

    并行指的是无论何时,多个线程都是在多个CPU核心上同时执行的,是真正的同时执行。

    da66efe882f3

    image

    分治法

    基本思想

    把一个规模大的问题划分为规模较小的子问题,然后分而治之,最后合并子问题的解得到原问题的解。

    步骤

    ①分割原问题;

    ②求解子问题;

    ③合并子问题的解为原问题的解。

    我们可以使用如下伪代码来表示这个步骤。

    if(任务很小){

    直接计算得到结果

    }else{

    分拆成N个子任务

    调用子任务的fork()进行计算

    调用子任务的join()合并计算结果

    }

    在分治法中,子问题一般是相互独立的,因此,经常通过递归调用算法来求解子问题。

    典型应用

    二分搜索

    大整数乘法

    Strassen矩阵乘法

    棋盘覆盖

    合并排序

    快速排序

    线性时间选择

    汉诺塔

    ForkJoin并行处理框架

    ForkJoin框架概述

    Java 1.7 引入了一种新的并发框架—— Fork/Join Framework,主要用于实现“分而治之”的算法,特别是分治之后递归调用的函数。

    ForkJoin框架的本质是一个用于并行执行任务的框架, 能够把一个大任务分割成若干个小任务,最终汇总每个小任务结果后得到大任务的计算结果。在Java中,ForkJoin框架与ThreadPool共存,并不是要替换ThreadPool

    其实,在Java 8中引入的并行流计算,内部就是采用的ForkJoinPool来实现的。例如,下面使用并行流实现打印数组元组的程序。

    public class SumArray {

    public static void main(String[] args){

    List numberList = Arrays.asList(1,2,3,4,5,6,7,8,9);

    numberList.parallelStream().forEach(System.out::println);

    }

    }

    这段代码的背后就使用到了ForkJoinPool。

    说到这里,可能有读者会问:可以使用线程池的ThreadPoolExecutor来实现啊?为什么要使用ForkJoinPool啊?ForkJoinPool是个什么鬼啊?! 接下来,我们就来回答这个问题。

    ForkJoin框架原理

    ForkJoin框架是从jdk1.7中引入的新特性,它同ThreadPoolExecutor一样,也实现了Executor和ExecutorService接口。它使用了一个无限队列来保存需要执行的任务,而线程的数量则是通过构造函数传入,如果没有向构造函数中传入指定的线程数量,那么当前计算机可用的CPU数量会被设置为线程数量作为默认值。

    ForkJoinPool主要使用分治法(Divide-and-Conquer Algorithm)来解决问题。典型的应用比如快速排序算法。这里的要点在于,ForkJoinPool能够使用相对较少的线程来处理大量的任务。比如要对1000万个数据进行排序,那么会将这个任务分割成两个500万的排序任务和一个针对这两组500万数据的合并任务。以此类推,对于500万的数据也会做出同样的分割处理,到最后会设置一个阈值来规定当数据规模到多少时,停止这样的分割处理。比如,当元素的数量小于10时,会停止分割,转而使用插入排序对它们进行排序。那么到最后,所有的任务加起来会有大概200万+个。问题的关键在于,对于一个任务而言,只有当它所有的子任务完成之后,它才能够被执行。

    所以当使用ThreadPoolExecutor时,使用分治法会存在问题,因为ThreadPoolExecutor中的线程无法向任务队列中再添加一个任务并在等待该任务完成之后再继续执行。而使用ForkJoinPool就能够解决这个问题,它就能够让其中的线程创建新的任务,并挂起当前的任务,此时线程就能够从队列中选择子任务执行。

    那么使用ThreadPoolExecutor或者ForkJoinPool,性能上会有什么差异呢?

    首先,使用ForkJoinPool能够使用数量有限的线程来完成非常多的具有父子关系的任务,比如使用4个线程来完成超过200万个任务。但是,使用ThreadPoolExecutor时,是不可能完成的,因为ThreadPoolExecutor中的Thread无法选择优先执行子任务,需要完成200万个具有父子关系的任务时,也需要200万个线程,很显然这是不可行的,也是很不合理的!!

    工作窃取算法

    假如我们需要做一个比较大的任务,我们可以把这个任务分割为若干互不依赖的子任务,为了减少线程间的竞争,于是把这些子任务分别放到不同的队列里,并为每个队列创建一个单独的线程来执行队列里的任务,线程和队列一一对应,比如A线程负责处理A队列里的任务。但是有的线程会先把自己队列里的任务干完,而其他线程对应的队列里还有任务等待处理。干完活的线程与其等着,不如去帮其他线程干活,于是它就去其他线程的队列里窃取一个任务来执行。而在这时它们会访问同一个队列,所以为了减少窃取任务线程和被窃取任务线程之间的竞争,通常会使用双端队列,被窃取任务线程永远从双端队列的头部拿任务执行,而窃取任务的线程永远从双端队列的尾部拿任务执行。

    工作窃取算法的优点:

    充分利用线程进行并行计算,并减少了线程间的竞争。

    工作窃取算法的缺点:

    在某些情况下还是存在竞争,比如双端队列里只有一个任务时。并且该算法会消耗更多的系统资源,比如创建多个线程和多个双端队列。

    Fork/Join框架局限性:

    对于Fork/Join框架而言,当一个任务正在等待它使用Join操作创建的子任务结束时,执行这个任务的工作线程查找其他未被执行的任务,并开始执行这些未被执行的任务,通过这种方式,线程充分利用它们的运行时间来提高应用程序的性能。为了实现这个目标,Fork/Join框架执行的任务有一些局限性。

    (1)任务只能使用Fork和Join操作来进行同步机制,如果使用了其他同步机制,则在同步操作时,工作线程就不能执行其他任务了。比如,在Fork/Join框架中,使任务进行了睡眠,那么,在睡眠期间内,正在执行这个任务的工作线程将不会执行其他任务了。

    (2)在Fork/Join框架中,所拆分的任务不应该去执行IO操作,比如:读写数据文件。

    (3)任务不能抛出检查异常,必须通过必要的代码来出来这些异常。

    ForkJoin框架的实现

    ForkJoin框架中一些重要的类如下所示。

    da66efe882f3

    image

    ForkJoinPool 框架中涉及的主要类如下所示。

    1.ForkJoinPool类

    实现了ForkJoin框架中的线程池,由类图可以看出,ForkJoinPool类实现了线程池的Executor接口。

    我们也可以从下图中看出ForkJoinPool的类图关系。

    da66efe882f3

    image

    其中,可以使用Executors.newWorkStealPool()方法创建ForkJoinPool。

    ForkJoinPool中提供了如下提交任务的方法。

    public void execute(ForkJoinTask> task)

    public void execute(Runnable task)

    public T invoke(ForkJoinTask task)

    public List> invokeAll(Collection extends Callable> tasks)

    public ForkJoinTask submit(ForkJoinTask task)

    public ForkJoinTask submit(Callable task)

    public ForkJoinTask submit(Runnable task, T result)

    public ForkJoinTask> submit(Runnable task)

    2.ForkJoinWorkerThread类

    实现ForkJoin框架中的线程。

    3.ForkJoinTask类

    ForkJoinTask封装了数据及其相应的计算,并且支持细粒度的数据并行。ForkJoinTask比线程要轻量,ForkJoinPool中少量工作线程能够运行大量的ForkJoinTask。

    ForkJoinTask类中主要包括两个方法fork()和join(),分别实现任务的分拆与合并。

    fork()方法类似于Thread.start(),但是它并不立即执行任务,而是将任务放入工作队列中。跟Thread.join()方法不同,ForkJoinTask的join()方法并不简单的阻塞线程,而是利用工作线程运行其他任务,当一个工作线程中调用join(),它将处理其他任务,直到注意到目标子任务已经完成。

    我们可以使用下图来表示这个过程。

    da66efe882f3

    image

    ForkJoinTask有3个子类:

    da66efe882f3

    image

    RecursiveAction:无返回值的任务。

    RecursiveTask:有返回值的任务。

    CountedCompleter:完成任务后将触发其他任务。

    4.RecursiveTask 类

    有返回结果的ForkJoinTask实现Callable。

    5.RecursiveAction类

    无返回结果的ForkJoinTask实现Runnable。

    6.CountedCompleter 类

    在任务完成执行后会触发执行一个自定义的钩子函数。

    ForkJoin示例程序

    package io.binghe.concurrency.example.aqs;

    import lombok.extern.slf4j.Slf4j;

    import java.util.concurrent.ForkJoinPool;

    import java.util.concurrent.Future;

    import java.util.concurrent.RecursiveTask;

    @Slf4j

    public class ForkJoinTaskExample extends RecursiveTask {

    public static final int threshold = 2;

    private int start;

    private int end;

    public ForkJoinTaskExample(int start, int end) {

    this.start = start;

    this.end = end;

    }

    @Override

    protected Integer compute() {

    int sum = 0;

    //如果任务足够小就计算任务

    boolean canCompute = (end - start) <= threshold;

    if (canCompute) {

    for (int i = start; i <= end; i++) {

    sum += i;

    }

    } else {

    // 如果任务大于阈值,就分裂成两个子任务计算

    int middle = (start + end) / 2;

    ForkJoinTaskExample leftTask = new ForkJoinTaskExample(start, middle);

    ForkJoinTaskExample rightTask = new ForkJoinTaskExample(middle + 1, end);

    // 执行子任务

    leftTask.fork();

    rightTask.fork();

    // 等待任务执行结束合并其结果

    int leftResult = leftTask.join();

    int rightResult = rightTask.join();

    // 合并子任务

    sum = leftResult + rightResult;

    }

    return sum;

    }

    public static void main(String[] args) {

    ForkJoinPool forkjoinPool = new ForkJoinPool();

    //生成一个计算任务,计算1+2+3+4

    ForkJoinTaskExample task = new ForkJoinTaskExample(1, 100);

    //执行一个任务

    Future result = forkjoinPool.submit(task);

    try {

    log.info("result:{}", result.get());

    } catch (Exception e) {

    log.error("exception", e);

    }

    }

    }

    展开全文
  • 分而治之In the branch of Computer Science and Engineering, Information Technology and all the associated branches among these fields the term "Divide and Conquer" is an algorithm design paradigm based...
  • 在软件工程中,分而治之就是,将一个大型的开发项目分成很多小块,将所分的小块交给相应的人去开发去管理。 就像将一个复杂问题转化成几个简单的问题,等简单的问题被相继的解决后,再拼装回来,解决这个问题。...
  • 背景 最近一直在看《算法图解》这本书,对里面提到的“分而治之”的算法思想很有兴趣。 什么是分而治之 我们在遇到问题时,无法通过现有的已知算法来解决,这个时候就可以尝试这种思路:1.先找到基线条件,这种条件...
  • 分而治之简而言之就是先分再治理(合并): 1、从头开始分(在线处理) 每输入一个变量就对变量进行处理(可以理解为对n个数不断分为1和后面的所有项),对分出来的那一个变量在线处理(治); 2、从中间开始分 if ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,688
精华内容 18,275
关键字:

分而治之

友情链接: 画图.rar