文档章节

mapreduce top n(转)

仙剑奇侠
 仙剑奇侠
发布于 2015/01/02 20:32
字数 1212
阅读 190
收藏 4

     在研究关于mapreduce实现topn时候,发现了这篇博文,感觉挺不错的,与大家一块分享。原博客:http://my.oschina.net/u/1378204/blog/343666

     

     在最初接触mapreduce时,top n 问题的解决办法是将mapreduce输出(排序后)放入一个集合中,取前n个,但这种写法过于简单,内存能够加载的集合的大小是有上限的,一旦数据量大,很容易出现内存溢出。
    今天在这里介绍另一种实现方式,当然这也不是最好的方式,不过正所谓一步一个脚印,迈好每一步,以后的步伐才能更坚定,哈哈说了点题外话。恩恩,以后还会有更好的方式

    需求,得到top 最大的前n条记录
    这里只给出一些核心的代码,其他job等配置的代码略

?

1
2
Configuration conf = new Configuration();
conf.setInt( "N" , 5 );

    初始化job之前需要 conf.setInt("N",5); 意在在mapreduce阶段读取N,N就代表着top N
    以下是map

?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
package com.lzz.one;
import java.io.IOException;
import java.util.Arrays;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Mapper;
 
 
/**
  * topN
*  #orderid,userid,payment,productid
* [root@x00 hd]# cat seventeen_a.txt
* 1,9819,100,121
* 2,8918,2000,111
* 3,2813,1234,22
* 4,9100,10,1101
* 5,3210,490,111
* 6,1298,28,1211
* 7,1010,281,90
* 8,1818,9000,20
* [root@x00 hd]# cat seventeen_b.txt
* 100,3333,10,100
* 101,9321,1000,293
* 102,3881,701,20
* 103,6791,910,30
* 104,8888,11,39
  
* 预测结果:(求 Top N=5 的结果)
* 1 9000
* 2 2000
* 3 1234
* 4 1000
* 5 910
  * @author Administrator
  *
  */
public class TopNMapper extends Mapper<LongWritable, Text, IntWritable, IntWritable>{
     int len;
     int top[];
     @Override
     public void setup(Context context) throws IOException,InterruptedException {
         len = context.getConfiguration().getInt( "N" , 10 );
         top = new int [len+ 1 ];
     }
  
     @Override
public void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
     String line = value.toString();
     String arr []= line.split( "," );
     if (arr != null && arr.length == 4 ){
         int pay = Integer.parseInt(arr[ 2 ]);
         add(pay);
     }
}
 
 
public void add( int pay){
     top[ 0 ] = pay;
     Arrays.sort(top);
}
  
@Override
public void cleanup(Context context) throws IOException,InterruptedException {
     for ( int i= 1 ;i<=len;i++){
         <span></span>context.write( new IntWritable(top[i]), new IntWritable(top[i]));
     <span></span>}
  }
  
}
 
  
  
  
  
  <div>
 
 
  
  
  
  
  </div>

    接下来是reduce

?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package com.lzz.one;
 
import java.io.IOException;
import java.util.Arrays;
 
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.mapreduce.Reducer;
 
public class TopNReduce extends Reducer<IntWritable, IntWritable, IntWritable, IntWritable>{
     int len;
     int top[];
     @Override
     public void setup(Context context)
             throws IOException, InterruptedException {
         len = context.getConfiguration().getInt( "N" , 10 );
         top = new int [len+ 1 ];
     }
     
     @Override
     public void reduce(IntWritable key, Iterable<IntWritable> values,
             Context context)
             throws IOException, InterruptedException {
         for (IntWritable val : values){
             add(val.get());
         }
     }
     
     public void add( int pay){
         top[ 0 ] = pay;
         Arrays.sort(top);
     }
     
     @Override
     public void cleanup(Context context)
             throws IOException, InterruptedException {
         for ( int i=len;i> 0 ;i--){
             context.write( new IntWritable(len-i+ 1 ), new IntWritable(top[i]));
         }
     }
}

    说一下逻辑,虽然画图比较清晰,但是时间有限,画图水平有限,只用语言来描述吧,希望能说的明白
    如果要取top 5,则应该定义一个长度为为6的数组,map所要做的事情就是将每条日志的那个需要排序的字段放入数组第一个元素中,调用Arrays.sort(Array[])方法可以将数组按照正序,从数字角度说是从小到大排序,比如第一条记录是9000,那么排序结果是[0,0,0,0,0,9000],第二条日志记录是8000,排序结果是[0,0,0,0,8000,9000],第三条日志记录是8500,排序结果是[0,0,0,8000,8500,9000],以此类推,每次放进去一个数字如果大于数组里面最小的元素,相当于将最小的覆盖掉了,也就是说数组中元素永远是拿到日志中最大的那些个记录
    ok,map将数组原封不动按照顺序输出,reduce接收到从每个map拿到的五个排好序的元素,在进行跟map一样的排序,排序后数组里面就是按照从小到大排好序的元素,将这些元素倒序输出就是最终我们要的结果了

    与之前的方式做个比较,之前的map做的事情很少,在reduce中排序后哪前5条,reduce的压力是很大的,要把所有的数据都处理一遍,而一般设置reduce的个数较少,一旦数据较多,reduce就会承受不了,悲剧了。而现在的方式巧妙的将reduce的压力转移到了map,而map是集群效应的,很多台服务器来做这件事情,减少了一台机器上的负担,每个map其实只是输出了5个元素而已,如果有5个map,其实reduce才对5*5个数据进行了操作,也就不会出现内存溢出等问题了

本文转载自:http://my.oschina.net/u/1378204/blog/343666

共有 人打赏支持
仙剑奇侠
粉丝 2
博文 6
码字总数 3056
作品 0
成都
程序员
私信 提问
MapReduce: 一个巨大的倒退

前言 databasecolumn 的数据库大牛们(其中包括PostgreSQL的最初伯克利领导:Michael Stonebraker)最近写了一篇评论当前如日中天的MapReduce技术的文章,引发剧烈的讨论。我抽空在这儿翻译一...

ddatsh
2011/11/04
4.4K
7
[转]MapReduce:超大机群上的简单数据处理

MapReduce:超大机群上的简单数据处理 摘要 MapReduce是一个编程模型,和处理,产生大数据集的相关实现.用户指定一个 map函数处理一个key/value对,从而产生中间的key/value对集.然后再指定一个r...

穿越星辰
2011/04/22
0
0
Hadoop实例:二度人脉与好友推荐

在新浪微博、人人网等社交网站上,为了使用户在网络上认识更多的朋友,社交网站往往提供类似“你可能感兴趣的人”、“间接关注推荐”等好友推荐的功能。一直很好奇这个功能是怎么实现的。 其...

intergret
2013/01/03
0
12
一文详解大规模数据计算处理原理及操作重点

作者介绍 李智慧,《大型网站技术架构:核心原理与案例分析》作者。曾供职于阿里巴巴与英特尔亚太研发中心,从事大型网站与大数据方面的研发工作,目前在做企业级区块链方面的开发工作。 大数...

DBAplus社群
08/07
0
0
Reduce连接(reduce-side joins)

如果没有一个 map-side join 技术适合我们的数据集,那么就需要在 MapReduce 中使用 shuffle 来排序和连接两个数据集。这称为 reduce-side joins,也叫”重分区连接”。 【例】基本的重分区连...

天行自息
11/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Netty handle方法周期 (四)

写了一个练习之后,发现自定义的助手类每次肯定是必须的,对于不同的业务逻辑需求,会写相对应的逻辑 最简单的查看Handle生命周期的方式,就是重写上级方法,看名字差不多应该可以知道方法的作用 ...

_大侠__
9分钟前
0
0
vue主动刷新页面及列表数据删除后的刷新实例

1.场景 在处理列表时,常常有删除一条数据或者新增数据之后需要重新刷新当前页面的需求。 2.遇到的问题 1. 用vue-router重新路由到当前页面,页面是不进行刷新的 2.采用window.reload(),或者...

前端小攻略
20分钟前
1
0
闲话高并发的那些神话,看京东架构师如何把它拉下神坛

高并发也算是这几年的热门词汇了,尤其在互联网圈,开口不聊个高并发问题,都不好意思出门。高并发有那么邪乎吗?动不动就千万并发、亿级流量,听上去的确挺吓人。但仔细想想,这么大的并发与...

James-
25分钟前
3
0
Emacs 系列:让我们拥抱 Emacs 和 org 模式

导读 我必须承认,在使用了几十年的 vim 后, 我被 Emacs 吸引了。长期以来,我一直对如何组织安排事情感到沮丧。我也有用过 GTD 和 ZTD 之类的方法,但是像邮件或是大型文件这样的事务真的很...

问题终结者
26分钟前
3
0
解析Node.js通过axios实现网络请求

本次给大家分享一篇node.js通过axios实现网络请求的方法,写的十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批评指正。 1、使用Npm 下载axios n...

前端攻城老湿
39分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部