MapReduce之幺半群

MapReduce之幺半群

首先先简单介绍一些概念

幺元

幺元即单位元，是集合里的一种特别的元，与该集合里的运算有关。当它和其他元素结合时，并不会改变那些元素。

幺半群

幺半群是一个存在幺元的半群

幺半群具有以下性质：

• 闭包：对于S中的所有a和b，运算a$o$b的结果也在S中
• 结合律：对于S中所有的a,b和c满足以下等式： $(a\circ b)\circ c=(a\circ (b\circ c)$
• 单位元：$\exists eϵS:\forall aϵS:e\circ a=a\circ e=a$
  此外，幺半群还具有幂等性和交换律等特性。

因为在之前的Mapeduce学习过程中并没有怎么使用Mapeduce的组合器，因此，在这次学习的过程中通过将不具有结合性的MapReduce运算转化为可结合的运算，对于充分利用组合起和提升MapReduce作业的性能具有重要作用。

幺半群和非幺半群示例

整数集最大值

集合S={0,1,2,…}上的求最大值运算定义了一个满足交换律的幺半群，其单位元为0：
MAX(a,MAX(b,c))=MAX(MAX(a,b),c)
MAX(a,0)=MAX(0,a)=a
MAX(a,b) $\in$ S

整数集减法

整数集上的减法运算不能构成一个幺半群，因为不满足结合律：
(1-2)-3 $\ne$ 1-(2-3)
(1-2)-3=-4
1-(2-3)=2
同理，整数集的加法和乘法可以构成一个可交换的幺半群，整数集均值和中位数并不能满足幺半群。

在这篇博客中，以计算均值为例，通过使用组合起与幺半群来提升计算性能。

整数集的均值

整数集的计算过程如下
MEAN(1,2,3,4,5)$\ne$MEAN(MEAN(1,2,3),MEAN(4,5))
MEAN(1,2,3,4,5)=$\frac{1+2+3+4+5}{5}$=3
MEAN(MEAN(1,2,3),MEAN(4,5))=MEAN(2,4.5)=$\frac{2+4.5}{2}$=3.25
这个结果当然有问题啊，所以可以这样修改
MEAN(MEAN(1,2,3),MEAN(4,5))=MEAN(MEAN(6,3),MEAN(9,2)=MEAN(15,5)=3

其中MEAN(6,3)表示 1+2+3=6，总共3个数字

样例数据

key1,1
key1,2
key1,3
key1,4
key1,5
key2,2
key2,4
key2,6
key2,8
key2,10
key3,3
key3,6
key3,9
key3,12
key3,15
key4,4
key4,8
key4,12
key4,16
key4,20
key5,5
key5,10
key5,15
key5,20
key5,25
通过MapReduce，来实现对不同的key求其均值

mapper阶段任务

该阶段主要是将不同的key及其对应的值提取出来，并记录每个不同的key出现的次数

mapper阶段编码

public class MeanMonoizedMapper extends Mapper<LongWritable,Text,Text,PairOfLongInt> {private final static PairOfLongInt reduceV=new PairOfLongInt();private final static Text reduceK=new Text();@Overridepublic void map(LongWritable key,Text value,Context context){String[] lines=value.toString().split(",");try{reduceK.set(lines[0]);reduceV.set(Long.parseLong(lines[1]),1);context.write(reduceK,reduceV);} catch (InterruptedException e) {e.printStackTrace();} catch (IOException e) {e.printStackTrace();}}
}

其中PairOfLongInt设计如下

public class PairOfLongInt implements WritableComparable<PairOfLongInt> {private long left;private int right;public PairOfLongInt(){}public PairOfLongInt(long left,int right){set(left,right);}public void set(long left,int right){this.left=left;this.right=right;}public long getLeft() {return left;}public void setLeft(long left) {this.left = left;}public int getRight() {return right;}public void setRight(int right) {this.right = right;}public int compareTo(PairOfLongInt o) {if(left==o.getLeft()){if(right<o.getRight()){return -1;}if(right>o.getRight()){return 1;}return 0;}if(left<o.getLeft()){return -1;}return 1;}public void write(DataOutput dataOutput) throws IOException {dataOutput.writeLong(left);dataOutput.writeInt(right);}public void readFields(DataInput dataInput) throws IOException {left=dataInput.readLong();right=dataInput.readInt();}
}

combiner阶段任务

主要是统计在该mapper下的和及每个key的个数

combiner阶段编码

public class MeanMonoizedCombiner extends Reducer<Text,PairOfLongInt, Text,PairOfLongInt> {@Overridepublic void reduce(Text key,Iterable<PairOfLongInt> values,Context contexxt){long sum=0;int count=0;for(PairOfLongInt pair:values){sum+=pair.getLeft();count+=pair.getRight();}try{contexxt.write(key,new PairOfLongInt(sum,count));} catch (InterruptedException e) {e.printStackTrace();} catch (IOException e) {e.printStackTrace();}}
}

reducer阶段任务

该阶段求最终的结果

reducer阶段编码

public class MeanMonoizedReducer extends Reducer<Text,PairOfLongInt, Text, DoubleWritable> {@Overridepublic void reduce(Text key,Iterable<PairOfLongInt> values,Context context){long sum=0;int count=0;for(PairOfLongInt pair:values){sum+=pair.getLeft();count+=pair.getRight();}try{context.write(key,new DoubleWritable(sum/count));} catch (InterruptedException e) {e.printStackTrace();} catch (IOException e) {e.printStackTrace();}}
}

驱动程序如下

public class Driver {public static void main(String[] args) throws Exception{Configuration conf=new Configuration();String[] otherArgs=new String[]{"input/MeanMonoized.txt","output"};Job job=new Job(conf,"MeanMonoized");job.setJarByClass(Driver.class);job.setMapperClass(MeanMonoizedMapper.class);job.setCombinerClass(MeanMonoizedCombiner.class);job.setReducerClass(MeanMonoizedReducer.class);job.setMapOutputKeyClass(Text.class);job.setMapOutputValueClass(PairOfLongInt.class);job.setOutputKeyClass(Text.class);job.setOutputValueClass(DoubleWritable.class);FileInputFormat.addInputPath(job,new Path(otherArgs[0]));FileOutputFormat.setOutputPath(job,new Path(otherArgs[1]));System.exit(job.waitForCompletion(true)?0:1);}
}

最终结果如下