Mapreduce TopK

 
思想比较简单,就是每个通过map来获取当前的数据块中的的topk个数据,然后将他们以相同的key值放到reduce中,最后通过reduce来对这n*k个数据排序并获得topk个数据。具体的就是建立一个k个大小的数组,一开始初始化为都是100(假定这里的100是最大的数),然后往里面插数据小的数据即可。
 
PS:有几个小细节以及当时写代码的时候出错的地方。
1 map和reduce都是在每个键值对来的时候会被调用。当时觉得应该把这k的数组放在哪,以及怎么初始化。如果放在map方法里面,那每次都会被初始化,岂不是白搞了。如果把这数组当作局部变量,那肯定是不行的,因为当作局部变量就无法实现存放k个数据了。只能存放当前的数据。后来查了资料发现,有个setup这个函数,就是用于mapper中的某些数据的初始化,这样就可以把数组作为mapper的属性,然后在setup中进行初始化了。
2 当我全部遍历完这个数据分片的数据后,并且已经获得了当前mapper中的topk了,我如何把数据传到reducer呢,最理想的就是在遍历完后才把数据发送过去,但是以前都是处理一个键值对就发送一个,然后查了下,发现有个cleanup函数,就是用于mapper或者reducer结束后用的,那么就可以通过这个函数来发送键值对了。
3 这是个逻辑上的问题,我这里的topk是选最小的几个,然后当时写的是,先将数组排序,然后从前往后查询,如果发现value<list[i]那么就将该数组中数据替换,但是这个有问题,例如有这样的
45
21
75
94
1
34
56
7
67
按照我一开始的逻辑是,
45,100,100
21,100,100显然这一步就错了,应该是21,45,100所以应该是从后往前的查询,每次查询能替换的最大的数据,而不是从前往后的查询替换最小的数据
 
具体代码:
Map
 
                 public void setup(Context context){
                                Configuration conf=context.getConfiguration();
                                 int k=Integer.parseInt(conf.get( "k" ));
                                 list =new int[k];
                                 for (int i=0;i<k;i++){
                                                 list [i]=100;
                                }
                }
                
                 public void cleanup(Context context) throws IOException, InterruptedException{
                                 for (int i=0;i< list. length ;i++){
                                                context.write( new IntWritable(0), new IntWritable( list[i]));
                                                System. out .println("                                 ");
                                                System. out .println("map is " + list[i]);
                                                System. out .println("                                 ");
                                }
                }
                
                 public void map(LongWritable ikey, Text ivalue, Context context)
                                                 throws IOException, InterruptedException {
                                Configuration conf=context.getConfiguration();
                                 int k=Integer.parseInt(conf.get( "k" ));
                                 int value=Integer.parseInt(ivalue.toString());
                                
                                Arrays. sort( list);
                                System. out .println("                                 ");
                                System. out .println("n is " + n);
                                System. out .println("                                 ");
 
                                                 for (int j=k-1;j>=0;j--){
                                                                 if (value<list [j]){
                                                                                 list [j]=value;
                                                                                 break ;
                                                                }
                                                }
                                
                                
                }
 
}
 
Reducer
 
                 public void setup(Context context){
                                Configuration conf=context.getConfiguration();
                                 int k=Integer.parseInt(conf.get( "k" ));
                                 list =new int[k];
                                 for (int i=0;i<k;i++){
                                                 list [i]=100;
                                }
                }
                
                 public void cleanup(Context context) throws IOException, InterruptedException{
                                Arrays. sort( list);
                                 for (int i=0;i< list. length ;i++){
                                                context.write( new IntWritable(i), new IntWritable( list[i]));
                                }
                }
                
                
                 public void reduce(IntWritable _key, Iterable<IntWritable> values, Context context)
                                                 throws IOException, InterruptedException {
                                 // process values
                                Configuration conf=context.getConfiguration();
                                 int k=Integer.parseInt(conf.get( "k" ));
                                 for (IntWritable val : values) {
                                                 /*
                                                System.out.println("                                 ");
                                                System.out.println("value is "+val.get());
                                                System.out.println("                                 ");
                                                */
                                                Arrays. sort( list);
 
                                                                 for (int j=k-1;j>=0;j--){
                                                                                 if (val.get()<list [j]){
                                                                                                 list [j]=val.get();
                                                                                                 break ;
                                                                                }
                                                                }
                                                                
                                                
                                }
                }
上一篇:【Swift】UIPresentationController的使用方法


下一篇:win7 资源管理器的背景色修改