关于在mapreduce框架中的两个矩阵相乘(A*B)的算法实现,有如下两种思路。。
第一,因为我们在学校课堂内的矩阵相乘的基本算法就是A的行与B的列相乘 当然要满足A的列的维数与B的行维数相同,才能满足相乘的条件。所以有如下基本思路:
让每个map任务计算A的一行乘以B的一列,最后由reduce进行求和输出。这是最原始的实现方法:
假设A(m*n) B(n*s)
map的输入的格式如下<<x,y>,<Ax,By>> 0=<x<m,0=<y<s,0=<z<n
其中 <x,y>是key,x代表A的行号,y代表B的列号,<<Ax,By>>是value,Ax代表A的第x行第z列的元素,By代表B的第y列的第z行的一个元素,
A的一行与B的一列输入到一个maptask中,我们只需要对每个键值对中的value的两个值相乘即可,输出一个<<x,y>,Ax*By>
然后到洗牌阶段,将相同的可以输入到一个Reduce task中,然后reduce只需对相同key的value列表进行Ax*By进行求和即可。这个算法说起来比较简单,但是如何控制split中的内容是主要的问题。
首先需要重写InputSplit,InputFormat,Partion,来控制数据的流动,在数据结构方面需要定义一个实现的WritableComparable借口的类来保存两个整数(因为前面的key和value都出现两个整数),而且对象可以排序。
IntPair.class实现
package com.zxx.matrix;
import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
import org.apache.hadoop.io.WritableComparable;
public class IntPair implements WritableComparable
{
private int right=0;
private int left=0;
public IntPair(){}
public IntPair(int right,int left){
this.right=right;
this.left=left;
}
public int getRight(){
return right;
}
public int getLeft(){
return left;
}
public void setRight(int right){
this.right=right;
}
public void setLeft(int left){
this.left=left;
}
public String toString(){
return left+","+right;
}
@Override
public void readFields(DataInput arg0) throws IOException
{
// TODO Auto-generated method stub
right=arg0.readInt();
left=arg0.readInt();
}
@Override
public void write(DataOutput arg0) throws IOException
{
// TODO Auto-generated method stub
arg0.writeInt(right);
arg0.writeInt(left);
}
@Override
public int compareTo(Object arg0)
{
// TODO Auto-generated method stub
IntPair o=(IntPair)arg0;
if(this.right<o.getRight())
{
return -1;
}else if (this.right>o.getRight()) {
return 1;
}else if (this.left<o.getLeft()) {
return -1;
}else if (this.left>o.getLeft()) {
return 1;
}
return 0;
}
}
InputSplit.class(样例)
在这个类中用一个ArrayWritable 来保存元素的位置信息以及具体的元素信息
public class matrixInputSplit extends InputSplit implements Writable
{
private IntPair[] t;//具体元素信息
private IntPair location;//key的值,元素位置信息
private ArrayWritable intPairArray;
public matrixInputSplit()
{
}
public matrixInputSplit(int row,matrix left,int col,matrix right)
{
//填充intPairArray
intPairArray=new ArrayWritable(IntPair.class);
t=new IntPair[4];
location=new IntPair(row,col);
for(int j=0;j<3;j++)
{
IntPair intPair=new IntPair();
intPair.setLeft(left.m[row][j]);
intPair.setRight(right.m[j][col]);
t[j]=intPair;
}
t[3]=location;
intPairArray.set(t);
}
@Override
public long getLength() throws IOException, InterruptedException
{
return 0;
}
@Override
public String[] getLocations() throws IOException, InterruptedException
{
return new String[]{}; //返回空 这样JobClient就不会从文件中读取split
}
@Override
public void readFields(DataInput arg0) throws IOException
{
this.intPairArray=new ArrayWritable(IntPair.class);
this.intPairArray.readFields(arg0);
}
@Override
public void write(DataOutput arg0) throws IOException
{
/*arg0.writeInt(t.length);
for(int i=0;i<t.length;i++)
{
t[i].write(arg0);
}*/
intPairArray.write(arg0);
}
public IntPair getLocation()
{
t=new IntPair[4];
try
{
t=(IntPair[])intPairArray.toArray();
} catch (Exception e)
{
System.out.println("toArray excption");
}
return t[3];
}
public IntPair[] getIntPairs()
{
t=new IntPair[4];
try
{
t=(IntPair[])intPairArray.toArray();
} catch (Exception e)
{
System.out.println("toArray excption");
}
IntPair[] intL=new IntPair[3];
for(int i=0;i<3;i++)
{
intL[i]=t[i];
}
return intL;
}
}
Inputformat.class
这个类比较简单,只需要实现getSplit方法即可,不过需要用户自定义一个方法就是从getInputfile获得的路径来解析矩阵,输入到split中即可。
matrixMul.class
public class MatrixNew
{
public static class MatrixMapper extends Mapper<IntPair, IntPair, IntPair, IntWritable>
{
public void map(IntPair key, IntPair value, Context context)
{
int left=0 ;
int right=0;
System.out.println("map is do");
left = value.getLeft();
right = value.getRight();
IntWritable result = new IntWritable(left * right); // key不变,
// value中的两个int相乘
try
{
context.write(key, result);
} catch (IOException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
} catch (InterruptedException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
} // 输出kv对
}
}
public static class MatrixReducer extends Reducer<IntPair, IntWritable, IntPair, IntWritable>
{
private IntWritable result = new IntWritable();
public void reduce(IntPair key, Iterable<IntWritable> values, Context context)
{
int sum = 0;
for (IntWritable val : values)
{
int v = val.get();
sum += v;
}
result.set(sum);
try
{
context.write(key, result);
} catch (IOException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
} catch (InterruptedException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
public static class FirstPartitioner extends Partitioner<IntPair, IntWritable>
{
public int getPartition(IntPair key, IntWritable value, int numPartitions)
{
int abs = Math.abs(key.getLeft()) % numPartitions;
// numPartitions是reduce线程的数量
return abs;
}
}
public static void main(String[] args) throws IOException, InterruptedException, ClassNotFoundException
{
Configuration conf=new Configuration();
new GenericOptionsParser(conf, args);
FileSystem fs=FileSystem.get(conf);
Job job = new Job(conf, "New Matrix Multiply Job ");
job.setJarByClass(MatrixNew.class);
job.setNumReduceTasks(1);
job.setInputFormatClass(matrixInputFormat.class);
job.setOutputFormatClass(TextOutputFormat.class);
job.setMapperClass(MatrixMapper.class);
job.setReducerClass(MatrixReducer.class);
job.setPartitionerClass(FirstPartitioner.class);
job.setMapOutputKeyClass(IntPair.class);
job.setMapOutputValueClass(IntWritable.class);
job.setOutputKeyClass(IntPair.class);
job.setOutputValueClass(IntWritable.class);
matrixInputFormat.setInputPath(args[0]);
FileOutputFormat.setOutputPath(job,new Path(fs.makeQualified(new Path("/newMartixoutput")).toString()));
boolean ok = job.waitForCompletion(true);
if(ok){ //删除临时文件
}
}
}
以上代码只是简单测试下。。如有问题欢迎大家指正!这里先谢过!
第二个方法就是矩阵分块相乘,这个算法网上有大牛已经给出了源代码。。。
分享到:
相关推荐
基于MapReduce的矩阵相乘算法代码及其使用
使用Hadoop MapReduce实现两个矩阵相乘算法
Hadoop mapreduce 实现MatrixMultiply矩阵相乘
基于mapreduc框架的稀疏矩阵相乘运算。
利用k_means聚类算法的MapReduce并行化实现,为学习hadoop的同学提供参考
Hadoop-MapReduce下的PageRank矩阵分块算法 高清完整中文版PDF下载
基于MapReduce框架一种文本挖掘算法的设计与实现
Hadoop-MapReduce下的PageRank矩阵分块算法
该算法结合数据划分的思想进行并行化改进,简化了生成候选项的连接步骤,仅需对事务数据库扫描两次,同时在计算过程中还能对事务进行压缩,从而进一步提高了算法的性能。通过两种算法在不同数据规模下算法性能的对比...
针对海量数据背景下K-means聚类结果不稳定和收敛速度较慢的问题,提出了基于MapReduce框架下的K-means改进算法。首先,为了能获得K-means聚类的初始簇数,利用凝聚层次聚类法对数据集进行聚类,并用轮廓系数对聚类...
基于MapReduce的Apriori算法代码及其使用
主要为大家详细介绍了基于MapReduce实现决策树算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
采用patyon基于MapReduce架构实现矩阵相乘,大数据离线运算,Map+Reduce架构,判断前后运算结果是否相同
摘要:为了提高k-nearestneighboralgorithm(KNN)算法处理大数据集的能力,本文利用MapReduce并行编程模型,同时结合KNN算法自
MapReduce下的Dijkstra并行算法研究.pdf
针对传统GSP算法需要多次扫描数据库、I/O开销巨大的缺点,提出了一种基于MapReduce编程框架的序列模式挖掘算法MR-GSP(GSP algorithm based on MapReduce)。MR-GSP算法将原序列数据库划分为多个子序列数据库并分发...
MapReduce实现单元最短路径算法.doc
用MapReduce实现KMeans算法,数据的读写都是在HDFS上进行的,在伪分布下运行没有问题。文档中有具体说明。
云计算MapReduce实现KNN算法,使用环境:在vmware虚拟机上安装unbuntu14系统,系统中安装hadoop。文件中包含有MapReduce以及KNN的java代码、包含训练数据的excel表格以及详细的教程文档,文档中手把手教到如何使用...
Mincemeat-node 是使用Node.js实现的极简MapReduce框架,可以快速的部署投入工作,免去Hadoop繁琐的配置,享受随心大数据。Mincemeatpy实现的是一种非常简单的MapReduce模型,仅仅实现了任务的分布计算,并没有类似...