MapReduce实现TopK算法（实战）

习读书之业，便当知读书之乐
存为善之心，不必邀为善之名

项目介绍

• 给定数据集data.csv，内含三列，格式如下

编号	时间	风速
WT2300	2015/9/1 0:00	3.34
WT2300	2015/9/1 0:10	3.12
…	…	…
WT2301	2015/6/18 6:00	0.73
…	…	…
WT2302	2015/11/30 23:50	3.32

• 求不同编号的风机每个月风速排名前十
• 需要得到的结果如下

风机编号-月份	排名前十的风速
WT0230020151	17.41,16.81,16.55,16.4,15.63,15.59,15.53,15.44,15.29,15.12
WT0230020152	17.42,16.82,16.79,16.5,16.48,16.35,16.1,16.07,16.05,15.99
…	…
WT02302201512	16.54,16.4,16.06,15.96,15.56,15.48,15.47,15.46,15.13,15.11

数据集下载

data.csv 提取码76h4

程序下载

• FanData.java 提取码yz96
• TopK.java 提取码nkjr

代码讲解

• FanData.java
  该类在Map阶段从按行读入的数据解析出FanData对象

package cn.neu.blog.topk;

public class FanData {
	
	private String fanNo;

	private String time;

	private String windSpeed;
	
	public void getInstance(String row) {
		String[] cols = row.split(",");
		this.fanNo = cols[0];
		this.time = cols[1];
		this.windSpeed = cols[2];
	}

	public String getFanNo() {
		return fanNo;
	}

	public void setFanNo(String fanNo) {
		this.fanNo = fanNo;
	}

	public String getTime() {
		return time;
	}

	public void setTime(String time) {
		this.time = time;
	}

	public String getWindSpeed() {
		return windSpeed;
	}

	public void setWindSpeed(String windSpeed) {
		this.windSpeed = windSpeed;
	}
	
	@Override
	public String toString() {
		return "fanNo=" + this.fanNo + ",time=" + this.time + ",windSpeed=" + this.windSpeed;
	}
}

• TopK.java
  • Map阶段
    Map阶段对从数据集中按行读入的数据进行解析，产生fanData对象，获得其风机编号、时间和风速，然后对时间进行分割，仅取年份和月份，将风机编号与分割后的时间进行连接，作为Map输出阶段的Key
    注意：这里将每一行读入的数据都输出了进入Shuffle阶段，程序运行效率低，而有些数据在Map阶段就可以判断不可能是前K的数据，可以在此阶段尝试使用TreeMap，自己动动脑筋~

public static class TopKMapper extends Mapper<Object, Text, Text, DoubleWritable> {
        private FanData fanData = new FanData();
        private static final int K = 10;

        protected void map(Object key, Text value, Context context) throws IOException, InterruptedException {
            fanData.getInstance(value.toString());
            String fanNo = fanData.getFanNo();
            String time = fanData.getTime();
            time = time.substring(0,7).replace("/", "");
            String strKey = fanNo + time;
            double windSpeed = Double.parseDouble(fanData.getWindSpeed());
            context.write(new Text(strKey), new DoubleWritable(windSpeed));
        }
    }

• Reduce阶段
  该阶段需要实例化一个TreeMap对象，用于对风速进行排序
  注意：该对象能对Double进行排序，但不能对DoubleWritable进行排序
  将Key对应的Values依次添加到TreeMap中，控制TreeMap的大小始终不超过K，若超过则将TreeMap第一个元素（最小的）剔除

public static class TopKReducer extends Reducer<Text, DoubleWritable, Text, Text> {
        private static final int K = 10;
        TreeMap<Double, Double> tm = new TreeMap<Double, Double>();
        StringBuffer sb = new StringBuffer();

        protected void reduce(Text key, Iterable<DoubleWritable> values, Context context) throws IOException, InterruptedException {
            tm = new TreeMap<Double, Double>();
            sb = new StringBuffer();
            for(DoubleWritable val:values){
                tm.put(val.get(), val.get());
                if(tm.size() > K){
                    tm.remove(tm.firstKey());
                }
            }
            for(Double ws : tm.descendingKeySet()) sb.append(ws).append(",");
            context.write(key, new Text(sb.toString().substring(0, sb.toString().lastIndexOf(","))));
        }
    }

• 主函数
  使用IDE运行该程序时需要设置参数
  otherArgs[0]为输入路径
  otherArgs[1]为输出路径

public static void main(String[] args) throws IOException, ClassNotFoundException, InterruptedException {
        System.setProperty("HADOOP_USER_NAME", "root");
        Configuration conf = new Configuration();
        FileSystem fs = FileSystem.newInstance(conf);
        String[] otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs();
        if(otherArgs.length != 2){
            System.err.println("Usage: topk <in> <out>");
            System.exit(2);
        }
        Path outPath = new Path(otherArgs[1]);
        if(fs.exists(outPath)){
            fs.delete(outPath, true);
        }
        Job job = Job.getInstance(conf, "topk");
        job.setJarByClass(TopK.class);
        job.setMapperClass(TopKMapper.class);
        job.setMapOutputKeyClass(Text.class);
        job.setMapOutputValueClass(DoubleWritable.class);
        job.setReducerClass(TopKReducer.class);
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(Text.class);
        FileInputFormat.addInputPath(job, new Path(otherArgs[0]));
        FileOutputFormat.setOutputPath(job, new Path(otherArgs[1]));
        System.exit(job.waitForCompletion(true) ? 0 : 1);
    }

运行结果示例

有疑问的朋友可以在下方留言或者私信我，我尽快回答
欢迎各路大神萌新指点、交流！
求关注！求点赞！求收藏！