文档章节

mapreduce top n(转)

仙剑奇侠
 仙剑奇侠
发布于 2015/01/02 20:32
字数 1212
阅读 188
收藏 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
成都
程序员
Hadoop实例:二度人脉与好友推荐

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

intergret
2013/01/03
0
12
[转]MapReduce:超大机群上的简单数据处理

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

穿越星辰
2011/04/22
0
0
2014-11-12--Hadoop的基础学习(三)--Hadoop中MapReduce框架入门

1.MapReduce的简单概念 百度百科:MapReduce是一种编程模型,用于大规模数据集(大于1TB)的并行运算。概念"Map(映射)"和"Reduce(归约)",和他们的主要思想,都是从函数式编程语言里借来的...

查封炉台
2014/11/16
0
8
一文详解大规模数据计算处理原理及操作重点

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

DBAplus社群
08/07
0
0
hadoop 学习笔记:mapreduce框架详解

这个觉得写得特别的详细,有一些细节可能要去看书,会理解的更好点,,,   Mapreduce初析   Mapreduce是一个计算框架,既然是做计算的框架,那么表现形式就是有个输入(input),mapre...

LIPING234
2013/10/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

秒杀网站系统设计详解

最近总有一些朋友问高并发问题,后来就想自己把一个秒杀系统作为例子详细分解一下,也是一个学习过程。 首先假设场景,预计该活动可能有1万人参加,那最大并发数为1万。 主要面对的问题分析:...

小海bug
28分钟前
2
0
TypeScript基础入门之装饰器(一)

转发 TypeScript基础入门之装饰器(一) 介绍 随着TypeScript和ES6中Classes的引入,现在存在某些场景需要额外的功能来支持注释或修改类和类成员。 装饰器提供了一种为类声明和成员添加注释和元...

durban
38分钟前
1
0
sed命令扩展使用操作

打印某行到某行之间的内容 假若文件test.txt的内容是: ertfff**[abcfd]123324444[rty]**fgfgf 怎么能截取 [abcfd]123324444[rty] 这一部分出来呢? 操作命令: 知道开始行和结...

野雪球
54分钟前
1
0
JVM内存笔记

Hotspot JVM 中的 Java 线程与原生操作系统线程有直接的映射关系。当线程本地存储、缓 冲区分配、同步对象、栈、程序计数器等准备好以后,就会创建一个操作系统原生线程。 Java 线程结束,原...

凌渡
今天
1
0
284. Peeking Iterator

Description Tag: Design Difficulties: Medium Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the pee......

52iSilence7
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部