精华内容
下载资源
问答
  • 分类算法--并行逻辑回归算法

    千次阅读 2015-03-19 14:16:04
    逻辑回归(Logistic Regression,简称LR)是机器学习中十分常用的一种分类算法,在互联网领域得到了广泛的应用,无论是在广告系统中进行CTR预估,推荐系统中的预估转换率,反垃圾系统中的识别垃圾内容……都可以看到...

    逻辑回归(Logistic Regression,简称LR)是机器学习中十分常用的一种分类算法,在互联网领域得到了广泛的应用,无论是在广告系统中进行CTR预估,推荐系统中的预估转换率,反垃圾系统中的识别垃圾内容……都可以看到它的身影。LR以其简单的原理和应用的普适性受到了广大应用者的青睐。实际情况中,由于受到单机处理能力和效率的限制,在利用大规模样本数据进行训练的时候往往需要将求解LR问题的过程进行并行化,本文从并行化的角度讨论LR的实现。

    1. LR的基本原理和求解方法

    LR模型中,通过特征权重向量对特征向量的不同维度上的取值进行加权,并用逻辑函数将其压缩到0~1的范围,作为该样本为正样本的概率。逻辑函数为,曲线如图1。


    图1 逻辑函数曲线

    给定M个训练样本,其中Xj={xji|i=1,2,…N} 为N维的实数向量(特征向量,本文中所有向量不作说明都为列向量);yj取值为+1或-1,为分类标签,+1表示样本为正样本,-1表示样本为负样本。在LR模型中,第j个样本为正样本的概率是:

    其中W是N维的特征权重向量,也就是LR问题中要求解的模型参数。

    求解LR问题,就是寻找一个合适的特征权重向量W,使得对于训练集里面的正样本,值尽量大;对于训练集里面的负样本,这个值尽量小(或

    尽量大)。用联合概率来表示:

    对上式求log并取负号,则等价于:

                                                    公式(1)

    公式(1)就是LR求解的目标函数。

    寻找合适的W令目标函数f(W)最小,是一个无约束最优化问题,解决这个问题的通用做法是随机给定一个初始的W0,通过迭代,在每次迭代中计算目标函数的下降方向并更新W,直到目标函数稳定在最小的点。如图2所示。


    图2 求解最优化目标函数的基本步骤

    不同的优化算法的区别就在于目标函数下降方向Dt的计算。下降方向是通过对目标函数在当前的W下求一阶倒数(梯度,Gradient)和求二阶导数(海森矩阵,Hessian Matrix)得到。常见的算法有梯度下降法、牛顿法、拟牛顿法。

    (1) 梯度下降法(Gradient Descent)

    梯度下降法直接采用目标函数在当前W的梯度的反方向作为下降方向:

    其中为目标函数的梯度,计算方法为:

    公式(2)

    (2) 牛顿法(Newton Methods)

    牛顿法是在当前W下,利用二次泰勒展开近似目标函数,然后利用该近似函数来求解目标函数的下降方向:。其中Bt为目标函数f(W)在Wt处的海森矩阵。这个搜索方向也称作牛顿方向。

    (3) 拟牛顿法(Quasi-Newton Methods):

    拟牛顿法只要求每一步迭代中计算目标函数的梯度,通过拟合的方式找到一个近似的海森矩阵用于计算牛顿方向。最早的拟牛顿法是DFP(1959年由W. C. Davidon提出,并由R. Fletcher和M. J. D. Powell进行完善)。DFP继承了牛顿法收敛速度快的优点,并且避免了牛顿法中每次迭代都需要重新计算海森矩阵的问题,只需要利用梯度更新上一次迭代得到的海森矩阵,但缺点是每次迭代中都需要计算海森矩阵的逆,才能得到牛顿方向。

    BFGS是由C. G. Broyden, R. Fletcher, D. Goldfarb和D. F. Shanno各自独立发明的一种方法,只需要增量计算海森矩阵的逆Ht=Bt-1,避免了每次迭代中的矩阵求逆运算。BFGS中牛顿方向表示为:

    L-BFGS(Limited-memory BFGS)则是解决了BFGS中每次迭代后都需要保存N*N阶海森逆矩阵的问题,只需要保存每次迭代的两组向量和一组标量即可:

    在L-BFGS的第t次迭代中,只需要两步循环既可以增量计算牛顿方向:

    2. 并行LR的实现

    由逻辑回归问题的求解方法中可以看出,无论是梯度下降法、牛顿法、拟牛顿法,计算梯度都是其最基本的步骤,并且L-BFGS通过两步循环计算牛顿方向的方法,避免了计算海森矩阵。因此逻辑回归的并行化最主要的就是对目标函数梯度计算的并行化。从公式(2)中可以看出,目标函数的梯度向量计算中只需要进行向量间的点乘和相加,可以很容易将每个迭代过程拆分成相互独立的计算步骤,由不同的节点进行独立计算,然后归并计算结果。

    将M个样本的标签构成一个M维的标签向量,M个N维特征向量构成一个M*N的样本矩阵,如图3所示。其中特征矩阵每一行为一个特征向量(M行),列为特征维度(N列)。


    图3 样本标签向量 & 特征向量

    如果将样本矩阵按行划分,将样本特征向量分布到不同的计算节点,由各计算节点完成自己所负责样本的点乘与求和计算,然后将计算结果进行归并,则实现了“按行并行的LR”。按行并行的LR解决了样本数量的问题,但是实际情况中会存在针对高维特征向量进行逻辑回归的场景(如广告系统中的特征维度高达上亿),仅仅按行进行并行处理,无法满足这类场景的需求,因此还需要按列将高维的特征向量拆分成若干小的向量进行求解。

     (1) 数据分割

    假设所有计算节点排列成m行n列(m*n个计算节点),按行将样本进行划分,每个计算节点分配M/m个样本特征向量和分类标签;按列对特征向量进行切分,每个节点上的特征向量分配N/n维特征。如图4所示,同一样本的特征对应节点的行号相同,不同样本相同维度的特征对应节点的列号相同。


    图4 并行LR中的数据分割

    一个样本的特征向量被拆分到同一行不同列的节点中,即:

    其中Xr,k表示第r行的第k个向量,X(r,c),k表示Xr,k在第c列节点上的分量。同样的,用Wc表示特征向量W在第c列节点上的分量,即:


    (2) 并行计算

    观察目标函数的梯度计算公式(公式(2)),其依赖于两个计算结果:特征权重向量Wt和特征向量Xj的点乘,标量和特征向量Xj的相乘。可以将目标函数的梯度计算分成两个并行化计算步骤和两个结果归并步骤:

    ① 各节点并行计算点乘,计算,其中k=1,2,…,M/m表示第t次迭代中节点(r,c)上的第k个特征向量与特征权重分量的点乘,Wc,t为第t次迭代中特征权重向量在第c列节点上的分量。

    ②对行号相同的节点归并点乘结果:


    计算得到的点乘结果需要返回到该行所有计算节点中,如图5所示。
                 
                                                               图5 点乘结果归并


    ③ 各节点独立算标量与特征向量相乘:

    G(r,c),t可以理解为由第r行节点上部分样本计算出的目标函数梯度向量在第c列节点上的分量。

    ④ 对列号相同的节点进行归并:

    Gc,t就是目标函数的梯度向量Gt在第c列节点上的分量,对其进行归并得到目标函数的梯度向量:

    这个过程如图6所示。


    图6 梯度计算结果归并

    综合上述步骤,并行LR的计算流程如图7所示。比较图1和图7,并行LR实际上就是在求解损失函数最优解的过程中,针对寻找损失函数下降方向中的梯度方向计算作了并行化处理,而在利用梯度确定下降方向的过程中也可以采用并行化(如L-BFGS中的两步循环法求牛顿方向)。


    图7 并行LR计算流程
    3. 实验及结果

    利用MPI,分别基于梯度下降法(MPI_GD)和L-BFGS(MPI_L-BFGS)实现并行LR,以Liblinear为基准,比较三种方法的训练效率。Liblinear是一个开源库,其中包括了基于TRON的LR(Liblinear的开发者Chih-Jen Lin于1999年创建了TRON方法,并且在论文中展示单机情况下TRON比L-BFGS效率更高)。由于Liblinear并没有实现并行化(事实上是可以加以改造的),实验在单机上进行,MPI_GD和MPI_L-BFGS均采用10个进程。

    实验数据是200万条训练样本,特征向量的维度为2000,正负样本的比例为3:7。采用十折交叉法比较MPI_GD、MPI_L-BFGS以及Liblinear的分类效果。结果如图8所示,三者几乎没有区别。


    图8 分类效果对比
    将训练数据由10万逐渐增加到200万,比较三种方法的训练耗时,结果如图9,MPI_GD由于收敛速度慢,尽管采用10个进程,单机上的表现依旧弱于Liblinear,基本上都需要30轮左右的迭代才能达到收敛;MPI_L-BFGS则只需要3~5轮迭代即可收敛(与Liblinear接近),虽然每轮迭代需要额外的开销计算牛顿方向,其收敛速度也要远远快于MPI_GD,另外由于采用多进程并行处理,耗时也远低于Liblinear。


    图9 训练耗时对比
    展开全文
  • 朴素贝叶斯分类并行算法

    千次阅读 2016-06-20 11:20:31
    NaiveBayesMain.java import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.fs.Path; import org.apache.hadoop.mapreduce.Job; import org.apache.hadoop.util.GenericOptionsParser;...

    NaiveBayesMain.java

    import org.apache.hadoop.conf.Configuration;
    import org.apache.hadoop.fs.Path;
    import org.apache.hadoop.mapreduce.Job;
    import org.apache.hadoop.util.GenericOptionsParser;
    import org.apache.hadoop.fs.FileSystem;
    import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
    import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
    import org.apache.hadoop.io.IntWritable;
    import org.apache.hadoop.io.Text;
    
    public class NaiveBayesMain
    {
    	public static void main(String[] args) throws Exception
    	{
    		Configuration conf = new Configuration();
    		String[] otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs();
    		FileSystem fs = FileSystem.get(conf);
    		Path path_train, path_temp, path_test, path_out;
    		if(otherArgs.length != 5)
    		{
    			System.err.println("Usage: NaiveBayesMain <dfs_path> <conf> <train> <test> <out>");
    			System.exit(2);
    		}
    
    		conf.set("conf", otherArgs[0] + "/" +otherArgs[1]);
    		conf.set("train", otherArgs[0] + "/" +otherArgs[2]);
    		conf.set("test", otherArgs[0] + "/" +otherArgs[3]);
    		conf.set("output", otherArgs[0] + "/" +otherArgs[4]);
    		
        	put2HDFS(otherArgs[1], otherArgs[0] + "/" + otherArgs[1], conf);
        	put2HDFS(otherArgs[2], otherArgs[0] + "/" + otherArgs[2], conf);
        	put2HDFS(otherArgs[3], otherArgs[0] + "/" + otherArgs[3], conf);
    		
    		path_train = new Path(otherArgs[0] + "/" + otherArgs[2]);
        	path_temp = new Path(otherArgs[0] + "/" + otherArgs[2] + ".train");
        	path_test = new Path(otherArgs[0] + "/" +otherArgs[3]);
        	path_out = new Path(otherArgs[0] + "/" + otherArgs[4]);
        	
    		{
    		Job job_train = new Job(conf, "naive bayse training");
    		job_train.setJarByClass(NaiveBayesMain.class);
    		job_train.setMapperClass(NaiveBayesTrain.TrainMapper.class);
    		job_train.setCombinerClass(NaiveBayesTrain.TrainReducer.class);
    		job_train.setReducerClass(NaiveBayesTrain.TrainReducer.class);
    		job_train.setOutputKeyClass(Text.class);
        	job_train.setOutputValueClass(IntWritable.class);
         	
        	FileInputFormat.setInputPaths(job_train, path_train);
        	if(fs.exists(path_temp))
        		fs.delete(path_temp, true);
        	FileOutputFormat.setOutputPath(job_train, path_temp);
        	if(job_train.waitForCompletion(true) == false)
        		System.exit(1);
        		
        	conf.set("train_result", otherArgs[0] + "/" +otherArgs[2] + ".train");
        	}
        	{
        	Job job_test = new Job(conf, "naive bayse testing");
        	job_test.setJarByClass(NaiveBayesTest.class);
        	job_test.setMapperClass(NaiveBayesTest.TestMapper.class);
        	job_test.setOutputKeyClass(Text.class);
        	job_test.setOutputValueClass(Text.class);
        	
        	FileInputFormat.setInputPaths(job_test, path_test);
        	if(fs.exists(path_out))
        		fs.delete(path_out, true);
        	FileOutputFormat.setOutputPath(job_test, path_out);
        	if(job_test.waitForCompletion(true) == false)
        		System.exit(1);
        	fs.delete(path_temp, true);
        	}
        	
        	getFromHDFS(otherArgs[0] + "/" + otherArgs[4], ".", conf);
        	
        	fs.close();
        	System.exit(0);
    	}
    	
    	
    	public static void put2HDFS(String src, String dst, Configuration conf) throws Exception
    	{
    		Path dstPath = new Path(dst);
    		FileSystem hdfs = dstPath.getFileSystem(conf);
    		
    		hdfs.copyFromLocalFile(false, true, new Path(src), new Path(dst));
    		
    	}
    	
    	public static void getFromHDFS(String src, String dst, Configuration conf) throws Exception
    	{
    		Path dstPath = new Path(dst);
    		FileSystem lfs = dstPath.getFileSystem(conf);
    		String temp[] = src.split("/");
    		Path ptemp = new Path(temp[temp.length-1]);
    		if(lfs.exists(ptemp));
    			lfs.delete(ptemp, true);
    		lfs.copyToLocalFile(true, new Path(src), dstPath);
    		
    	}
    }
    

    NaiveBayesTrain.java

    import java.util.Scanner;
    import java.io.IOException;
    import java.util.ArrayList;
    
    
    import org.apache.hadoop.conf.Configuration;
    
    import org.apache.hadoop.mapreduce.Mapper;
    import org.apache.hadoop.mapreduce.Reducer;
    
    import org.apache.hadoop.io.IntWritable;
    import org.apache.hadoop.io.Text;
    
    public class NaiveBayesTrain
    {
    	public static class TrainMapper
    		extends Mapper<Object, Text, Text, IntWritable>
    	{
    		public NaiveBayesConf nBConf;
    		private final static IntWritable one = new IntWritable(1);
    		private Text word;
    		
    		public void setup(Context context) 
    		{
    			try{
    			nBConf = new NaiveBayesConf();
    			Configuration conf = context.getConfiguration();
    			nBConf.ReadNaiveBayesConf(conf.get("conf"), conf);
    			}
    			catch(Exception ex)
    			{
    				ex.printStackTrace();
    				System.exit(1);
    			}
    			System.out.println("setup");
    		}
    		public void map(Object key, Text value, Context context)
    			throws IOException, InterruptedException 
    		{
    			Scanner scan = new Scanner(value.toString());
    			String str, vals[], temp;
    			int i;
    			word = new Text();
    			while(scan.hasNextLine())
    			{
    				str = scan.nextLine();
    				vals = str.split(" ");
    				word.set(vals[0]);
    				context.write(word, one);
    				for(i = 1; i<vals.length; i++)
    				{
    					word = new Text();
    					temp = vals[0] + "#" + nBConf.proNames.get(i-1);
    					temp += "#" + vals[i];
    					word.set(temp);					
    					context.write(word, one);
    				}
    			}
    		}
    	}
    	
    	public static class TrainReducer
    		extends Reducer<Text,IntWritable,Text,IntWritable>
    	{
    		private IntWritable result = new IntWritable();
    		public void reduce(Text key, Iterable<IntWritable> values, 
            	Context context) throws IOException, InterruptedException 
    		{
    			int sum = 0;
    			for (IntWritable val : values) 
    			{
    				sum += val.get();
    			}
    			result.set(sum);
    			context.write(key, result);
            }
    	}
    }
    
    NaiveBayesTest.java

    import java.util.Scanner;
    import java.io.IOException;
    import java.util.HashMap;
    
    import org.apache.hadoop.conf.Configuration;
    import org.apache.hadoop.mapreduce.Mapper;
    import org.apache.hadoop.mapreduce.Reducer;
    import org.apache.hadoop.io.IntWritable;
    import org.apache.hadoop.io.Text;
    
    public class NaiveBayesTest
    {
    	public static class TestMapper 
    		extends Mapper<Object, Text, Text, Text>
    	{
    		public NaiveBayesConf nBConf;
    		public NaiveBayesTrainData nBTData;
    		public void setup(Context context)
    		{			
    			try{
    			Configuration conf = context.getConfiguration();
    			
    			nBConf = new NaiveBayesConf();
    			nBConf.ReadNaiveBayesConf(conf.get("conf"), conf);
    			nBTData = new NaiveBayesTrainData();
    			nBTData.getData(conf.get("train_result"), conf);
    			}
    			catch(Exception ex)
    			{
    				ex.printStackTrace();
    				System.exit(1);
    			}
    		}
    		
    		public void map(Object key, Text value, Context context)
    			throws IOException, InterruptedException 
    		{
    			Scanner scan = new Scanner(value.toString());
    			String str, vals[], temp;
    			int i,j,k,fxyi,fyi,fyij,maxf,idx;
    			Text id;
    			Text cls;
    			
    			while(scan.hasNextLine())
    			{
    				str = scan.nextLine();
    				vals = str.split(" ");
    				maxf = -100;
    				idx = -1;
    				for(i = 0; i<nBConf.class_num; i++)
    				{
    					fxyi = 1;
    					String cl = nBConf.classNames.get(i);
    					Integer integer = nBTData.freq.get(cl);
    					if(integer == null)
    						fyi = 0;
    					else
    						fyi = integer.intValue();
    					for(j = 1; j<vals.length; j++)
    					{
    						temp = cl + "#" + nBConf.proNames.get(j-1) + "#" + vals[j];
    						
    						integer = nBTData.freq.get(temp);
    						if(integer == null)
    							fyij = 0;
    						else
    							fyij = integer.intValue();
    						fxyi = fxyi*fyij;
    					}
    					if(fyi*fxyi > maxf)
    					{
    						maxf = fyi*fxyi;
    						idx = i;
    					}
    				}
    				id = new Text(vals[0]);
    				cls = new Text(nBConf.classNames.get(idx));
    				context.write(id, cls);
    			}
    		}
    	}
    }
    

    NaiveBayesConf.java

    import java.util.ArrayList;
    import java.util.Scanner;
    import java.io.File; 
    import java.io.FileNotFoundException;
    
    import org.apache.hadoop.fs.FSDataInputStream;
    import org.apache.hadoop.fs.Path;
    import org.apache.hadoop.fs.FileSystem;
    import org.apache.hadoop.conf.Configuration;
    
    public class NaiveBayesConf
    {
    	public int dimen;
    	public int class_num;
    	public ArrayList<String> classNames;
    	public ArrayList<String> proNames;
    	public ArrayList<Integer>	proRanges;
    	
    	public NaiveBayesConf()
    	{
    		dimen = class_num = 0;
    		classNames = new ArrayList<String>();
    		proNames = new ArrayList<String>();
    		proRanges = new ArrayList<Integer>();
    	}
    	
    	public void ReadNaiveBayesConf(String file, Configuration conf) throws Exception
    	{	
    		Path conf_path = new Path(file);
    		FileSystem hdfs = conf_path.getFileSystem(conf);
    		FSDataInputStream fsdt = hdfs.open(conf_path);
    		Scanner scan = new Scanner(fsdt);
    		String str = scan.nextLine();
    		String[] vals = str.split(" ");
    		
    		class_num = Integer.parseInt(vals[0]);
    		
    		int i;
    		
    		for(i = 1; i<vals.length; i++)
    		{
    			classNames.add(vals[i]);
    		}
    		
    		str = scan.nextLine();
    		vals = str.split(" ");
    		dimen = Integer.parseInt(vals[0]);
    		
    		for(i = 1; i<vals.length; i+=2)
    		{
    			proNames.add(vals[i]);
    			proRanges.add(new Integer(vals[i+1]));
    		}
    		fsdt.close();
    		scan.close();
    	}
    }
    
    NaiveBayesTrainData.java
    import java.util.ArrayList;
    import java.util.Scanner;
    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.io.File;
    import java.io.IOException;
    import java.io.FileNotFoundException;
    import java.util.HashMap;
    
    import org.apache.hadoop.fs.FSDataInputStream;
    import org.apache.hadoop.fs.Path;
    import org.apache.hadoop.fs.FileSystem;
    import org.apache.hadoop.conf.Configuration;
    import org.apache.hadoop.fs.FileStatus;
    //功能:读取指定路径下输出文件"part-..."并添加到HashMap
    public class NaiveBayesTrainData
    {
    	public HashMap<String, Integer> freq;
    
    	public NaiveBayesTrainData()
    	{
    		freq = new HashMap<String, Integer>();
    	}
    
    	public void getData(String file, Configuration conf) throws IOException
    	{
    		int i;
    		Path data_path = new Path(file);
    		Path file_path;
    		String temp[], line;
    		FileSystem hdfs = data_path.getFileSystem(conf);
    		
    		FileStatus[] status = hdfs.listStatus(data_path);
    		
    		for(i = 0; i<status.length; i++)
    		{
    			file_path = status[i].getPath();			
    			if(hdfs.getFileStatus(file_path).isDir() == true)
    				continue;
    			line = file_path.toString();
    			temp = line.split("/");
    			if(temp[temp.length-1].substring(0,5).equals("part-") == false)
    				continue;
    			System.err.println(line);
    			FSDataInputStream fin = hdfs.open(file_path);
    			InputStreamReader inr = new InputStreamReader(fin);
    			BufferedReader bfr = new BufferedReader(inr);
    			while((line = bfr.readLine()) != null)
    			{	
    				String res[] = line.split("\t");
    				freq.put(res[0], new Integer(res[1]));
    				System.out.println(line);
    			}
    			bfr.close();
    			inr.close();
    			fin.close();
    		}
    	}
    	
    }
    
    NBayes.conf
    4 cl1 cl2 cl3 cl4
    3 p1 12 p2 16 p3 17
    

    NBayes.train

    cl1 5 6 7
    cl2 3 8 4
    cl1 2 5 2
    cl3 7 8 7
    cl4 3 8 2
    cl4 9 2 7
    cl2 1 8 5
    cl5 2 9 4
    cl3 10 3 4
    cl1 4 5 6
    cl3 4 6 7
    


    NBayes.test
    1 5 6 7
    2 1 8 5
    3 2 9 4
    4 10 3 4
    5 4 5 6
    6 3 8 4
    7 2 5 2
    8 7 8 7
    9 3 8 2
    10 9 2 7
    11 4 6 7
    
    train-map-output.txt
    trainmapinput:cl1 5 6 7
    trainmapoutput:<cl1,1>
    trainmapoutput:<cl1#p1#5,1>
    trainmapoutput:<cl1#p2#6,1>
    trainmapoutput:<cl1#p3#7,1>
    trainmapinput:cl2 3 8 4
    trainmapoutput:<cl2,1>
    trainmapoutput:<cl2#p1#3,1>
    trainmapoutput:<cl2#p2#8,1>
    trainmapoutput:<cl2#p3#4,1>
    trainmapinput:cl1 2 5 2
    trainmapoutput:<cl1,1>
    trainmapoutput:<cl1#p1#2,1>
    trainmapoutput:<cl1#p2#5,1>
    trainmapoutput:<cl1#p3#2,1>
    trainmapinput:cl3 7 8 7
    trainmapoutput:<cl3,1>
    trainmapoutput:<cl3#p1#7,1>
    trainmapoutput:<cl3#p2#8,1>
    trainmapoutput:<cl3#p3#7,1>
    trainmapinput:cl4 3 8 2
    trainmapoutput:<cl4,1>
    trainmapoutput:<cl4#p1#3,1>
    trainmapoutput:<cl4#p2#8,1>
    trainmapoutput:<cl4#p3#2,1>
    trainmapinput:cl4 9 2 7
    trainmapoutput:<cl4,1>
    trainmapoutput:<cl4#p1#9,1>
    trainmapoutput:<cl4#p2#2,1>
    trainmapoutput:<cl4#p3#7,1>
    trainmapinput:cl2 1 8 5
    trainmapoutput:<cl2,1>
    trainmapoutput:<cl2#p1#1,1>
    trainmapoutput:<cl2#p2#8,1>
    trainmapoutput:<cl2#p3#5,1>
    trainmapinput:cl5 2 9 4
    trainmapoutput:<cl5,1>
    trainmapoutput:<cl5#p1#2,1>
    trainmapoutput:<cl5#p2#9,1>
    trainmapoutput:<cl5#p3#4,1>
    trainmapinput:cl3 10 3 4
    trainmapoutput:<cl3,1>
    trainmapoutput:<cl3#p1#10,1>
    trainmapoutput:<cl3#p2#3,1>
    trainmapoutput:<cl3#p3#4,1>
    trainmapinput:cl1 4 5 6
    trainmapoutput:<cl1,1>
    trainmapoutput:<cl1#p1#4,1>
    trainmapoutput:<cl1#p2#5,1>
    trainmapoutput:<cl1#p3#6,1>
    trainmapinput:cl3 4 6 7
    trainmapoutput:<cl3,1>
    trainmapoutput:<cl3#p1#4,1>
    trainmapoutput:<cl3#p2#6,1>
    trainmapoutput:<cl3#p3#7,1>

    train-reduce-output.txt

    cl1	3
    cl1#p1#2	1
    cl1#p1#4	1
    cl1#p1#5	1
    cl1#p2#5	2
    cl1#p2#6	1
    cl1#p3#2	1
    cl1#p3#6	1
    cl1#p3#7	1
    cl2	2
    cl2#p1#1	1
    cl2#p1#3	1
    cl2#p2#8	2
    cl2#p3#4	1
    cl2#p3#5	1
    cl3	3
    cl3#p1#10	1
    cl3#p1#4	1
    cl3#p1#7	1
    cl3#p2#3	1
    cl3#p2#6	1
    cl3#p2#8	1
    cl3#p3#4	1
    cl3#p3#7	2
    cl4	2
    cl4#p1#3	1
    cl4#p1#9	1
    cl4#p2#2	1
    cl4#p2#8	1
    cl4#p3#2	1
    cl4#p3#7	1
    cl5	1
    cl5#p1#2	1
    cl5#p2#9	1
    cl5#p3#4	1
    test-mapreduce-output.txt
    1	cl1
    10	cl4
    11	cl3
    2	cl2
    3	cl1
    4	cl3
    5	cl1
    6	cl2
    7	cl1
    8	cl3
    9	cl4





    展开全文
  • 并行细化算法

    千次阅读 2010-08-07 16:53:00
    http://hi.baidu.com/conglingks/blog/item/1ee6aade65d2015dcdbf1a22.html<br /><br />细化算法分类:...迭代方法依据其检查像素的方法又可以再分成串行算法并行算法,在串行算法中,是否删除像素在每次

    http://hi.baidu.com/conglingks/blog/item/1ee6aade65d2015dcdbf1a22.html

    细化算法的分类:

             依据是否使用迭代运算可以分为两类:第一类是非迭代算法,一次即产生骨架,如基于距离变换的方法。游程长度编码细化等。第二类是迭代算法,即重复删除图像 边缘满足一定条件的像素,最终得到单像素宽带骨架。迭代方法依据其检查像素的方法又可以再分成串行算法和并行算法,在串行算法中,是否删除像素在每次迭代 的执行中是固定顺序的,它不仅取决于前次迭代的结果,也取决于本次迭代中已处理过像素点分布情况,而在并行算法中,像素点删除与否与像素值图像中的顺序无 关,仅取决于前次迭代的结果。在经典细化算法发展的同时,起源于图像集合运算的形态学细化算法也得到了快速的发展。

             Hilditch、Pavlidis、Rosenfeld细化算法:这类算法则是在程序中直接运算,根据运算结果来判定是否可以删除点的算法,差别在于不同算法的判定条件不同。

             其中Hilditch算法使用于二值图像,比较普通,是一般的算法; Pavlidis算法通过并行和串行混合处理来实现,用位运算进行特定模式的匹配,所得的骨架是8连接的,使用于0-1二值图像 ;Rosenfeld算法是一种并行细化算法,所得的骨架形态是8-连接的,使用于0-1二值图像 。 后两种算法的效果要更好一些,但是处理某些图像时效果一般,第一种算法使用性强些。

             索引表细化算法:经过预处理后得到待细化的图像是0、1二值图像。像素值为1的是需要细化的部分,像素值为0的是背景区域。基于索引表的算法就是依据一定 的判断依据,所做出的一张表,然后根据魔鬼要细化的点的八个邻域的情况查询,若表中元素是1,若表中元素是1,则删除该点(改为背景),若是0则保留。因 为一个像素的8个邻域共有256中可能情况,因此,索引表的大小一般为256。

    图象细化算法代码:

    下面是我在网上搜索到的一些细化算法的源码,只是为了自己学习方便,可能有错误。

    【来 源】:http ://blog.csdn.net/byxdaz/archive/2006/02/27/610835.aspx

    /
    //Hilditch细化算法
    //功能:对图象进行细化
    //参数:image:代表图象的一维数组
    // lx:图象宽度
    // ly:图象高度
    // 无返回值
    void ThinnerHilditch(void *image, unsigned long lx, unsigned long ly)
    {
    char *f, *g;
    char n[10];
    unsigned int counter;
    short k, shori, xx, nrn;
    unsigned long i, j;
    long kk, kk11, kk12, kk13, kk21, kk22, kk23, kk31, kk32, kk33, size;
    size = (long)lx * (long)ly;
    g = (char *)malloc(size);

    if(g == NULL)
    {
    printf("error in allocating memory!/n");
    return;
    }

    f = (char *)image;
    for(i=0; i<lx; i++)
    {
    for(j=0; j<ly; j++)
    {
    kk="i"*ly+j;
    if(f[kk]!=0)
    {
    f[kk]=1;
    g[kk]=f[kk];
    }
    }
    }

    counter = 1;

    do
    {
    printf("%4d*",counter);
    counter++;
    shori = 0;

    for(i=0; i<lx; i++)
    {
    for(j=0; j<ly; j++)
    {
    kk = i*ly+j;
    if(f[kk]<0)
    f[kk] = 0;
    g[kk]= f[kk];
    }
    }

    for(i=1; i<lx-1; i++)
    {
    for(j=1; j<ly-1; j++)
    {
    kk="i"*ly+j;

    if(f[kk]!=1)
    continue;

    kk11 = (i-1)*ly+j-1;
    kk12 = kk11 + 1;
    kk13 = kk12 + 1;
    kk21 = i*ly+j-1;
    kk22 = kk21 + 1;
    kk23 = kk22 + 1;
    kk31 = (i+1)*ly+j-1;
    kk32 = kk31 + 1;
    kk33 = kk32 + 1;

    if((g[kk12]&&g[kk21]&&g[kk23]&&g[kk32])!=0)
    continue;

    nrn = g[kk11] + g[kk12] + g[kk13] + g[kk21] + g[kk23] +
    g[kk31] + g[kk32] + g[kk33];

    if(nrn <= 1)
    {
    f[kk22] = 2;
    continue;
    }

    n[4] = f[kk11];
    n[3] = f[kk12];
    n[2] = f[kk13];
    n[5] = f[kk21];
    n[1] = f[kk23];
    n[6] = f[kk31];
    n[7] = f[kk32];
    n[8] = f[kk33];
    n[9] = n[1];
    xx = 0;

    for(k=1; k<8; k="k"+2)
    {
    if((!n[k])&&(n[k+1]||n[k+2]))
    xx++;
    }

    if(xx!=1)
    {
    f[kk22] = 2;
    continue;
    }

    if(f[kk12] == -1)
    {
    f[kk12] = 0;
    n[3] = 0;
    xx = 0;

    for(k=1; k<8; k="k"+2)
    {
    if((!n[k])&&(n[k+1]||n[k+2]))
    xx++;
    }

    if(xx != 1)
    {
    f[kk12] = -1;
    continue;
    }

    f[kk12] = -1;
    n[3] = -1;
    }

    if(f[kk21]!=-1)
    {
    f[kk22] = -1;
    shori = 1;
    continue;
    }

    f[kk21] = 0;
    n[5] = 0;
    xx = 0;

    for(k=1; k<8; k="k"+2)
    {
    if((!n[k])&&(n[k+1]||n[k+2]))
    {
    xx++;
    }
    }

    if(xx == 1)
    {
    f[kk21] = -1;
    f[kk22] = -1;
    shori =1;
    }
    else
    f[kk21] = -1;
    }
    }
    }while(shori);

    free(g);
    }




    /
    //Pavlidis细化算法
    //功能:对图象进行细化
    //参数:image:代表图象的一维数组
    // lx:图象宽度
    // ly:图象高度
    // 无返回值
    void ThinnerPavlidis(void *image, unsigned long lx, unsigned long ly)
    {
    char erase, n[8];
    char *f;
    unsigned char bdr1,bdr2,bdr4,bdr5;
    short c,k,b;
    unsigned long i,j;
    long kk,kk1,kk2,kk3;
    f = (char*)image;

    for(i=1; i<lx-1; i++)
    {
    for(j=1; j<ly-1; j++)
    {
    kk = i*ly + j;
    if(f[kk])
    f[kk] = 1;
    }
    }

    for(i=0, kk1=0, kk2=ly-1; i<lx; i++, kk1+=ly, kk2+=ly)
    {
    f[kk1]=0;
    f[kk2]=0;
    }

    for(j=0, kk=(lx-1)*ly; j<ly; j++,kk++)
    {
    f[j]=0;
    f[kk]=0;
    }

    c="5";
    erase =1;
    while(erase)
    {
    c++;
    for(i=1; i<lx-1; i++)
    {
    for(j=1; j<ly-1; j++)
    {
    kk="i"*ly+j;
    if(f[kk]!=1)
    continue;

    kk1 = kk-ly -1;
    kk2 = kk1 + 1;
    kk3 = kk2 + 1;
    n[3] = f[kk1];
    n[2] = f[kk2];
    n[1] = f[kk3];
    kk1 = kk - 1;
    kk3 = kk + 1;
    n[4] = f[kk1];
    n[0] = f[kk3];
    kk1 = kk + ly -1;
    kk2 = kk1 + 1;
    kk3 = kk2 + 1;
    n[5] = f[kk1];
    n[6] = f[kk2];
    n[7] = f[kk3];

    bdr1 =0;
    for(k=0; k<8; k++)
    {
    if(n[k]>=1)
    bdr1|=0x80>>k;
    }

    if((bdr1&0252)== 0252)
    continue;
    f[kk] = 2;
    b="0";

    for(k=0; k<=7; k++)
    {
    b+=bdr1&(0x80>>k);
    }

    if(b<=1)
    f[kk]=3;

    if((bdr1&0160)!=0&&(bdr1&07)!=0&&(bdr1&0210)==0)
    f[kk]=3;
    else if((bdr1&&0301)!=0&&(bdr1&034)!=0&&(bdr1&042)==0)
    f[kk]=3;
    else if((bdr1&0202)==0 && (bdr1&01)!=0)
    f[kk]=3;
    else if((bdr1&0240)==0 && (bdr1&0100)!=0)
    f[kk]=3;
    else if((bdr1&050)==0 && (bdr1&020)!=0)
    f[kk]=3;
    else if((bdr1&012)==0 && (bdr1&04)!=0)
    f[kk]=3;
    }
    }

    for(i=1; i<lx-1; i++)
    {
    for(j=1; j<ly-1; j++)
    {
    kk = i*ly + j;
    if(!f[kk])
    continue;

    kk1 = kk - ly -1;
    kk2 = kk1 + 1;
    kk3 = kk2 + 1;
    n[3] = f[kk1];
    n[2] = f[kk2];
    n[1] = f[kk3];
    kk1 = kk - 1;
    kk2 = kk + 1;
    n[4] = f[kk1];
    n[0] = f[kk3];
    kk1 = kk + ly -1;
    kk2 = kk1 + 1;
    kk3 = kk2 + 1;
    n[5] = f[kk1];
    n[6] = f[kk2];
    n[7] = f[kk3];
    bdr1 = bdr2 =0;

    for(k=0; k<=7; k++)
    {
    if(n[k]>=1)
    bdr1|=0x80>>k;
    if(n[k]>=2)
    bdr2|=0x80>>k;
    }

    if(bdr1==bdr2)
    {
    f[kk] = 4;
    continue;
    }

    if(f[kk]!=2)
    continue;

    if((bdr2&0200)!=0 && (bdr1&010)==0 &&
    ((bdr1&0100)!=0 &&(bdr1&001)!=0 ||
    ((bdr1&0100)!=0 ||(bdr1 & 001)!=0) &&
    (bdr1&060)!=0 &&(bdr1&06)!=0))
    {
    f[kk] = 4;
    }

    else if((bdr2&040)!=0 && (bdr1&02)==0 &&
    ((bdr1&020)!=0 && (bdr1&0100)!=0 ||
    ((bdr1&020)!=0 || (bdr1&0100)!=0) &&
    (bdr1&014)!=0 && (bdr1&0201)!=0))
    {
    f[kk] = 4;
    }

    else if((bdr2&010)!=0 && (bdr1&0200)==0 &&
    ((bdr1&04)!=0 && (bdr1&020)!=0 ||
    ((bdr1&04)!=0 || (bdr1&020)!=0) &&
    (bdr1&03)!=0 && (bdr1&0140)!=0))
    {
    f[kk] = 4;
    }

    else if((bdr2&02)!=0 && (bdr1&040)==0 &&
    ((bdr1&01)!=0 && (bdr1&04)!=0 ||
    ((bdr1&01)!=0 || (bdr1&04)!=0) &&
    (bdr1&0300)!=0 && (bdr1&030)!=0))
    {
    f[kk] = 4;
    }
    }
    }

    for(i=1; i<lx-1; i++)
    {
    for(j=1; j<ly-1; j++)
    {
    kk = i*ly + j;
    if(f[kk]!=2)
    continue;
    kk1 = kk - ly -1;
    kk2 = kk1 + 1;
    kk3 = kk2 + 1;
    n[3] = f[kk1];
    n[2] = f[kk2];
    n[1] = f[kk3];
    kk1 = kk - 1;
    kk2 = kk + 1;
    n[4] = f[kk1];
    n[0] = f[kk3];
    kk1 = kk + ly -1;
    kk2 = kk1 + 1;
    kk3 = kk2 + 1;
    n[5] = f[kk1];
    n[6] = f[kk2];
    n[7] = f[kk3];
    bdr4 = bdr5 =0;
    for(k=0; k<=7; k++)
    {
    if(n[k]>=4)
    bdr4|=0x80>>k;
    if(n[k]>=5)
    bdr5|=0x80>>k;
    }
    if((bdr4&010) == 0)
    {
    f[kk] = 5;
    continue;
    }
    if((bdr4&040) == 0 && bdr5 ==0)
    {
    f[kk] = 5;
    continue;
    }
    if(f[kk]==3||f[kk]==4)
    f[kk] = c;
    }
    }

    erase = 0;
    for(i=1; i<lx-1; i++)
    {
    for(j=1; j<ly-1; j++)
    {
    kk = i*ly +j;
    if(f[kk]==2||f[kk] == 5)
    {
    erase = 1;
    f[kk] = 0;
    }
    }
    }
    }
    }



    /
    //Rosenfeld细化算法
    //功能:对图象进行细化
    //参数:image:代表图象的一维数组
    // lx:图象宽度
    // ly:图象高度
    // 无返回值
    void ThinnerRosenfeld(void *image, unsigned long lx, unsigned long ly)
    {
    char *f, *g;
    char n[10];
    char a[5] = {0, -1, 1, 0, 0};
    char b[5] = {0, 0, 0, 1, -1};
    char nrnd, cond, n48, n26, n24, n46, n68, n82, n123, n345, n567, n781;
    short k, shori;
    unsigned long i, j;
    long ii, jj, kk, kk1, kk2, kk3, size;
    size = (long)lx * (long)ly;

    g = (char *)malloc(size);
    if(g==NULL)
    {
    printf("error in alocating mmeory!/n");
    return;
    }

    f = (char *)image;
    for(kk=0l; kk<size; kk++)
    {
    g[kk] = f[kk];
    }

    do
    {
    shori = 0;
    for(k=1; k<=4; k++)
    {
    for(i=1; i<lx-1; i++)
    {
    ii = i + a[k];

    for(j=1; j<ly-1; j++)
    {
    kk = i*ly + j;

    if(!f[kk])
    continue;

    jj = j + b[k];
    kk1 = ii*ly + jj;

    if(f[kk1])
    continue;

    kk1 = kk - ly -1;
    kk2 = kk1 + 1;
    kk3 = kk2 + 1;
    n[3] = f[kk1];
    n[2] = f[kk2];
    n[1] = f[kk3];
    kk1 = kk - 1;
    kk3 = kk + 1;
    n[4] = f[kk1];
    n[8] = f[kk3];
    kk1 = kk + ly - 1;
    kk2 = kk1 + 1;
    kk3 = kk2 + 1;
    n[5] = f[kk1];
    n[6] = f[kk2];
    n[7] = f[kk3];

    nrnd = n[1] + n[2] + n[3] + n[4]
    +n[5] + n[6] + n[7] + n[8];
    if(nrnd<=1)
    continue;

    cond = 0;
    n48 = n[4] + n[8];
    n26 = n[2] + n[6];
    n24 = n[2] + n[4];
    n46 = n[4] + n[6];
    n68 = n[6] + n[8];
    n82 = n[8] + n[2];
    n123 = n[1] + n[2] + n[3];
    n345 = n[3] + n[4] + n[5];
    n567 = n[5] + n[6] + n[7];
    n781 = n[7] + n[8] + n[1];

    if(n[2]==1 && n48==0 && n567>0)
    {
    if(!cond)
    continue;
    g[kk] = 0;
    shori = 1;
    continue;
    }

    if(n[6]==1 && n48==0 && n123>0)
    {
    if(!cond)
    continue;
    g[kk] = 0;
    shori = 1;
    continue;
    }

    if(n[8]==1 && n26==0 && n345>0)
    {
    if(!cond)
    continue;
    g[kk] = 0;
    shori = 1;
    continue;
    }

    if(n[4]==1 && n26==0 && n781>0)
    {
    if(!cond)
    continue;
    g[kk] = 0;
    shori = 1;
    continue;
    }

    if(n[5]==1 && n46==0)
    {
    if(!cond)
    continue;
    g[kk] = 0;
    shori = 1;
    continue;
    }

    if(n[7]==1 && n68==0)
    {
    if(!cond)
    continue;
    g[kk] = 0;
    shori = 1;
    continue;
    }

    if(n[1]==1 && n82==0)
    {
    if(!cond)
    continue;
    g[kk] = 0;
    shori = 1;
    continue;
    }

    if(n[3]==1 && n24==0)
    {
    if(!cond)
    continue;
    g[kk] = 0;
    shori = 1;
    continue;
    }

    cond = 1;
    if(!cond)
    continue;
    g[kk] = 0;
    shori = 1;
    }
    }

    for(i=0; i<lx; i++)
    {
    for(j=0; j<ly; j++)
    {
    kk = i*ly + j;
    f[kk] = g[kk];
    }
    }
    }
    }while(shori);

    free(g);
    }




    /
    //基于索引表的细化细化算法
    //功能:对图象进行细化
    //参数:lpDIBBits:代表图象的一维数组
    // lWidth:图象高度
    // lHeight:图象宽度
    // 无返回值
    BOOL WINAPI ThiningDIBSkeleton (LPSTR lpDIBBits, LONG lWidth, LONG lHeight)
    {
    //循环变量
    long i;
    long j;
    long lLength;

    unsigned char deletemark[256] = {
    0,0,0,0,0,0,0,1, 0,0,1,1,0,0,1,1,
    0,0,0,0,0,0,0,0, 0,0,1,1,1,0,1,1,
    0,0,0,0,0,0,0,0, 1,0,0,0,1,0,1,1,
    0,0,0,0,0,0,0,0, 1,0,1,1,1,0,1,1,
    0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0, 1,0,0,0,1,0,1,1,
    1,0,0,0,0,0,0,0, 1,0,1,1,1,0,1,1,
    0,0,1,1,0,0,1,1, 0,0,0,1,0,0,1,1,
    0,0,0,0,0,0,0,0, 0,0,0,1,0,0,1,1,
    1,1,0,1,0,0,0,1, 0,0,0,0,0,0,0,0,
    1,1,0,1,0,0,0,1, 1,1,0,0,1,0,0,0,
    0,1,1,1,0,0,1,1, 0,0,0,1,0,0,1,1,
    0,0,0,0,0,0,0,0, 0,0,0,0,0,1,1,1,
    1,1,1,1,0,0,1,1, 1,1,0,0,1,1,0,0,
    1,1,1,1,0,0,1,1, 1,1,0,0,1,1,0,0
    };//索引表

    unsigned char p0, p1, p2, p3, p4, p5, p6, p7;
    unsigned char *pmid, *pmidtemp;
    unsigned char sum;
    int changed;
    bool bStart = true;
    lLength = lWidth * lHeight;
    unsigned char *pTemp = (unsigned char *)malloc(sizeof(unsigned char) * lWidth * lHeight);

    // P0 P1 P2
    // P7 P3
    // P6 P5 P4

    while(bStart)
    {
    bStart = false;
    changed = 0;

    //首先求边缘点(并行)
    pmid = (unsigned char *)lpDIBBits + lWidth + 1;
    memset(pTemp, (BYTE) 0, lLength);
    pmidtemp = (unsigned char *)pTemp + lWidth + 1;
    for(i = 1; i < lHeight -1; i++)
    {
    for(j = 1; j < lWidth - 1; j++)
    {
    if( *pmid == 0)
    {
    pmid++;
    pmidtemp++;
    continue;
    }

    p3 = *(pmid + 1);
    p2 = *(pmid + 1 - lWidth);
    p1 = *(pmid - lWidth);
    p0 = *(pmid - lWidth -1);
    p7 = *(pmid - 1);
    p6 = *(pmid + lWidth - 1);
    p5 = *(pmid + lWidth);
    p4 = *(pmid + lWidth + 1);

    sum = p0 & p1 & p2 & p3 & p4 & p5 & p6 & p7;
    if(sum == 0)
    {
    *pmidtemp = 1;
    }

    pmid++;
    pmidtemp++;
    }
    pmid++;
    pmid++;
    pmidtemp++;
    pmidtemp++;
    }

    //现在开始串行删除
    pmid = (unsigned char *)lpDIBBits + lWidth + 1;
    pmidtemp = (unsigned char *)pTemp + lWidth + 1;

    for(i = 1; i < lHeight -1; i++)
    {
    for(j = 1; j < lWidth - 1; j++)
    {
    if( *pmidtemp == 0)
    {
    pmid++;
    pmidtemp++;
    continue;
    }

    p3 = *(pmid + 1);
    p2 = *(pmid + 1 - lWidth);
    p1 = *(pmid - lWidth);
    p0 = *(pmid - lWidth -1);
    p7 = *(pmid - 1);
    p6 = *(pmid + lWidth - 1);
    p5 = *(pmid + lWidth);
    p4 = *(pmid + lWidth + 1);

    p1 *= 2;
    p2 *= 4;
    p3 *= 8;
    p4 *= 16;
    p5 *= 32;
    p6 *= 64;
    p7 *= 128;

    sum = p0 | p1 | p2 | p3 | p4 | p5 | p6 | p7;
    if(deletemark[sum] == 1)
    {
    *pmid = 0;
    bStart = true;
    }

    pmid++;
    pmidtemp++;
    }

    pmid++;
    pmid++;
    pmidtemp++;
    pmidtemp++;
    }
    }

    return true;
    }

    展开全文
  • 并行算法基本概念

    2017-12-20 14:25:59
    并行算法分类 并行算法的特征 并行算法的速度和效率 并行算法分类 Task parallelism and Data parallelism 任务并行和数据并行   Task parallelism:对任务进行并行化处理,每个核进行不同的操作。  Data ...

    并行算法基本概念


    本文主要包含如下内容:


    并行算法的分类


    Task parallelism and Data parallelism 任务并行和数据并行

      Task parallelism:对任务进行并行化处理,每个核进行不同的操作。

      Data parallelism:对数据进行并行化处理,每个核对不同数据进行类似的操作。

    Shared-memory and Distributed-memory 共享内存与分离式内存

      Shared-memory:内核可以共享计算机的内存

      Distributed-memory:内核只能够访问自己的私有内存

    Shared-memory and Distributed-memory


    并行算法的特征


    Communication 通信

      每个内核需要对该核的算法输入数据和计算结果的数据进行通信、传输。

    Load balancing 负载均衡

      为了加快运算速度,希望每个核完成运算时间基本一致,因此希望达到负载均衡。

    Synchronization 同步

      因为每个内核之间存在数据通信,所以需要等待所需数据的计算结果。


    并行算法的速度和效率


    Speedup

      p= Number of cores (内核数目)
      T serial = Serial run-time (串行运行时间)
      T parallel = Parallel run-time (并行运行时间)

    Tparallel=TserialP 

    S=TserialTparallel 

    Efficiency

    E=SP=TserialTparallelP=TserialPTparallel

    Tparallel=TserialP+Toverhead

      许多并行程序是通过将进程/线程之间的串行程序的工作分开,并添加必要的“并行开销”,例如互斥或通信来开发的。此外,随着问题大小的增加,T_overhead通常比T_serial慢得多。 进程/线程有更多的工作要做,因此协调进程/线程工作的相对时间应该更少。

    展开全文
  • 并行程序开发主要在于并行程序的设计、调试、维护和监控。 一、并行程序开发环境 现在研究重点是扩充现有的编译系统的并行语言功能,主要为: 数据级并行(利用Fortran等开发); 任务级并行(利用MPI、Linda等开发...
  • 并行计算及并行算法

    万次阅读 多人点赞 2018-06-13 22:27:31
    一、并行计算  简单地说,并行计算就是在并行计算机上所做的计算。从普通意义上讲,它和常说的高性能计算、超级计算等是同义词。并行计算的初衷是为了努力仿真自然世界中一个序列中含有众多同时发生的、复杂且相关...
  • 今年的课程中增加了,并行算法的课程,我一看,一门课程都挂上“算法”了,肯定厉害呀。这我可要认真学习它。 我把我自己的见解和大家分享一下,要是有错误的地方一定要指出啊。 这是我画的一个思维导图,好像是...
  • 并行算法

    千次阅读 2005-10-18 21:35:00
    今天为blog加了个分类并行算法。因为这学期我们开了这门课,它是高性能及分布式计算的基础,而且我发现他的程序结构非常有意思。想想能让多台计算机同时运行的你的程序,那有多爽,而让我惊讶的是MPICH2这个库实现...
  • 数据挖掘算法——常用分类算法总结

    万次阅读 多人点赞 2019-06-17 10:55:22
    常用分类算法总结分类算法总结NBC算法LR算法SVM算法ID3算法C4.5 算法C5.0算法KNN 算法ANN 算法 分类算法总结 分类是在一群已经知道类别标号的样本中,训练一种分类器,让其能够对某种未知的样本进行分类。分类算法...
  • 并行算法的设计基础

    2019-07-05 22:31:56
    并行算法的定义和分类 并行算法:一些可同时执行的诸进程的集合,这些进程互相作用和协调动作从而达到给定问题的求解。 并行算法分类 数值计算与非数值计算 同步算法和异步算法 分布算法 确定算法和随机算法 ...
  • 并行算法设计与分析课程总结 第一讲:概念及目标 并行算法的意义 提高性能的主要手段 现状 并行计算分类 并行计算互联网络 并行计算存储组织 Brent定理(work-time) PRAM上并行求和算法
  • 文章目录1. 并行元启发式算法的作用2. 并行基于单一解的元启发式算法3. 并行基于总体的元启发式算法...实现并行元启发式算法有两种方式:①从元启发式算法的角度来观察,依据单基和群基的并行元启发式算法来划分视图...
  • 并行算法的基本原理

    千次阅读 2015-09-05 16:30:02
    并行算法的基本原理 并行算法就是用多台处理机联合求解问题的方法和步骤,其执行过程是指将给定的问题首先分解成若干个尽量相互独立的子问题,然后使用多台计算机同时求解它,从而最终求得原问题的解。并行算法是...
  • 分类算法总结

    千次阅读 2018-05-21 15:37:12
    本文先系统的介绍一下机器学习中的分类算法,主要目录如下:常用分类算法Bayes朴素贝叶斯的优缺点朴素贝叶斯的公式Decision Tree决策树的优缺点决策树公式SVM支持向量机的优缺点支持向量机的公式KNNK近邻的优缺点K...
  • 在充分理解整个算法流程情况下就能够实现并行计算。 在模型层面一般有:交叉验证每个模型可以独立训练;网格搜索超参每个模型也可以单独训练;还有Bagging类算法。 更细粒度的层面:一般需要理解算法流程,如...
  • 算法---->并行算法

    千次阅读 2013-05-20 16:32:53
    并行算法 一、并行算法 什么是并行算法? 它可理解为: 适合于在某类并行计算机上求解问题和处理数据的算法, 是一些可同时执行的诸进程的集合, 这些进程相互作用和协调作用, 从而达到对给定问题的求解。 二、并行...
  • 并行计算分类

    千次阅读 2016-10-13 18:39:20
    并行计算分类
  • 各种分类算法比较

    千次阅读 2016-04-11 11:16:01
    最近在处理数据的时候,使用分类算法,为使用合适的分类算法,对各分类算法仔细研究了一番,而且在网上了这篇博文,对分类算法的优缺点比较简单明了,推荐学习一下。 1. 决策树(Decision Trees)的优缺点 ...
  • 基于MapReduce的并行算法设计

    千次阅读 2014-11-03 19:46:21
    这是中国大学MOOC中的大数据算法课程笔记
  • 判断是否为欧拉图的并行算法

    千次阅读 2013-11-16 18:15:44
    分类: 分布式与并行计算 算法 欧拉图: 一个图为欧拉图,当且公当有一条回路经过图的每一条边且恰好经过一次。...欧拉定理表明:一个图为欧拉图,当且仅当...下面给出复杂度为O(Log(N)) 并行算法,注意这里只给
  • 并行程序的编程模型、运行环境、调试环境等都要比串行程序复杂...并行算法研究要以硬件,即并行计算机为依托,并行计算机性能的发挥要依靠优秀并行算法的设计的实现。所以本文,并行算法研究现状及其相关问题的综述,将
  • 各种分类算法的比较

    千次阅读 2015-12-30 14:07:05
    面试的时候,经常会被问到一些分类算法的优劣比较。看到一些有用的相关文章,总结下来仅供参考: Source 1. http://sigvc.org/bbs/thread-3323-1-1.html How do you know what machine learning algorithm to ...
  • 在Alpha-Beta算法并行化的过程中,一个较为困难的问题是判断从哪里开始并行搜索,因为一个分支的搜索可能会发现并行进行的另一个搜索完全可以避免.正因为如此,Alpha-Beta算法是一个很难并行算法. 虽然仿真可能...
  • 常见分类算法优缺点

    千次阅读 2018-10-21 21:36:54
    机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。通常最开始我们都会选择大家普遍认同的算法,诸如SVM...
  • 并行算法设计--Foster的设计方法论

    千次阅读 2017-07-31 20:56:48
    a 原始任务数至少比目标并行计算机上的处理器数高一个数量级(如果该条件不能满足的话,则后面的设计将受到很大限制) b 冗余计算和冗余数据结构存储最小化(如果该条件不能满足的话,则该设计 在问题规模增加的...
  • 各种分类算法的优缺点

    千次阅读 2016-07-25 12:45:01
    原文对一些常用的分类算法,如决策树、SVM、朴素贝叶斯、adaboost、KNN等都提到了,总结得比较好,这里增加了一些自己的理解(文中斜体标明)。 1决策树(Decision Trees)的优缺点 决策树的优点: 一、 
  • 分类算法简介

    千次阅读 2019-06-06 22:15:36
    9 各种分类算法比较 根据这篇论文所得出的结论, Calibrated boosted trees的性能最好,随机森林第二,uncalibrated bagged trees第三,calibratedSVMs第四, uncalibrated neural nets第五。 性能较差的是朴素...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 76,854
精华内容 30,741
关键字:

并行分类算法