`
lt200819
  • 浏览: 187440 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

MapReduce求Top K的算法

 
阅读更多

 

今天去百度面试,这么简单的题做法都有问题,悲哀啊,mark一下。

估计要和百度失之交臂了,悔恨。

其实当时有想法了的,不过被面试官问了一句“放内存够大吗?”一下打消了这个想法。愁啊。

算法如下。不知道对不对。回去再研究下

 

package com.bupt.mapreduce;

 

 /**

 *

  */

 

 import org.apache.hadoop.conf.Configuration;

 import org.apache.hadoop.conf.Configured;

 import org.apache.hadoop.fs.Path;

 import org.apache.hadoop.io.IntWritable;

 import org.apache.hadoop.io.LongWritable;

 import org.apache.hadoop.io.NullWritable;

 import org.apache.hadoop.io.Text;

 import org.apache.hadoop.mapreduce.Job;

 import org.apache.hadoop.mapreduce.Mapper;

 import org.apache.hadoop.mapreduce.Reducer;

 import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;

 import org.apache.hadoop.mapreduce.lib.input.TextInputFormat;

 import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;

 import org.apache.hadoop.mapreduce.lib.output.TextOutputFormat;

 import org.apache.hadoop.util.Tool;

 import org.apache.hadoop.util.ToolRunner;

 

 import java.io.IOException;

 import java.util.TreeMap;

 

 //利用MapReduce求最大值海量数据中的K个数

 public class Top_k_new extends Configured implements Tool {

 

     public static class MapClass extends Mapper<LongWritable, Text, NullWritable, Text> {

         public static final int K = 100;

         private TreeMap<Integer, Text> fatcats = new TreeMap<Integer, Text>();

         public void map(LongWritable key, Text value, Context context)

                 throws IOException, InterruptedException {

 

             String[] str = value.toString().split(",", -2);

             int temp = Integer.parseInt(str[8]);

             fatcats.put(temp, value);

             if (fatcats.size() > K)

                 fatcats.remove(fatcats.firstKey())

         }

         @Override

         protected void cleanup(Context context) throws IOException,  InterruptedException {

             for(Text text: fatcats.values()){

                 context.write(NullWritable.get(), text);

             }

         }

     }

 

     public static class Reduce extends Reducer<NullWritable, Text, NullWritable, Text> {

         public static final int K = 100;

         private TreeMap<Integer, Text> fatcats = new TreeMap<Integer, Text>();

         public void reduce(NullWritable key, Iterable<Text> values, Context context)

                 throws IOException, InterruptedException {

             for (Text val : values) {

                 String v[] = val.toString().split("\t");

                 Integer weight = Integer.parseInt(v[1]);

                 fatcats.put(weight, val);

                 if (fatcats.size() > K)

                     fatcats.remove(fatcats.firstKey());

             }

             for (Text text: fatcats.values())

                 context.write(NullWritable.get(), text);

         }

     }

 

     public int run(String[] args) throws Exception {

         Configuration conf = getConf();

         Job job = new Job(conf, "TopKNum");

         job.setJarByClass(Top_k_new.class);

         FileInputFormat.setInputPaths(job, new Path(args[0]));

         FileOutputFormat.setOutputPath(job, new Path(args[1]));

         job.setMapperClass(MapClass.class);

        // job.setCombinerClass(Reduce.class);

         job.setReducerClass(Reduce.class);

         job.setInputFormatClass(TextInputFormat.class);

         job.setOutputFormatClass(TextOutputFormat.class);

         job.setOutputKeyClass(NullWritable.class);

         job.setOutputValueClass(Text.class);

         System.exit(job.waitForCompletion(true) ? 0 : 1);

         return 0;

     }

     public static void main(String[] args) throws Exception {

         int res = ToolRunner.run(new Configuration(), new Top_k_new(), args);

         System.exit(res);

     }

 

 }

 

分享到:
评论

相关推荐

    基于MapReduce实现物品协同过滤算法(ItemCF)

    5. **相似度计算**:在Reduce阶段,我们计算每对物品的相似度,这一步可能涉及到一些优化技巧,如采样或者Top-K策略,以减少计算量。 6. **推荐生成**:最后,对于每个用户,我们找出其已评分物品的相似物品,并...

    基于Java的Hadoop HDFS和MapReduce实践案例设计源码

    内容涵盖HDFS的JAVA API操作,如文件读取、写入、删除、元数据查询和文件列表等,以及MapReduce编程模型的多个应用,包括求平均数、Join操作、TopK算法、二次排序,并涉及自定义InputFormat、OutputFormat和shuflle...

    MapReduce中高效的Top-k天际线计算

    本文的创新之处在于将Top-k天际线计算与MapReduce框架相结合,设计了一种新颖的算法。之前的研究存在的问题包括I/O开销大、缺乏进步性(即逐步剔除非支配数据点的能力)、以及集中式分布而非分布式。而MR-DTKS算法的...

    MapReduce环境下面向用户偏好的top-k连接查询处理方法

    ### MapReduce环境下面向用户偏好的top-k连接查询处理方法 #### 一、研究背景与意义 随着互联网技术的快速发展和大数据时代的到来,如何高效地处理海量数据成为了研究的热点。传统的数据库管理系统难以应对大数据...

    大数据应用-基于大数据的推荐算法研究.pptx

    此外,论文还探讨了一种基于项目层次结构相似性的推荐算法,这种方法利用层次结构来度量项目间的相似度,并结合最短路径算法Dijkstra和TopK思想找到最相关的项目。通过与其他算法的对比,展示了其在某些场景下的优势...

    面试常见基础算法题总结

    10. **Top K问题**:最小堆可以实时维护K个最小元素,适用于在线问题。最大堆配合反序操作可用于找到最大的K个元素。空间允许时,还可以一次性将所有元素放入数组,使用快速选择或堆排序。 11. **位图(Bitmap)**...

    《数据算法Hadoop Spark大数据处理技巧》PDF 带目录!!

    目录 第1章二次排序:简介 19 第2章二次排序:详细示例 42 第3章 Top 10 列表 54 第4章左外连接 96 第5章反转排序 127 第6章移动平均 137 第7章购物篮分析 155 第8章共同好友 182 第9章使用MapReduce实现推荐引擎 ...

    大数据工作面试练习题 BAT大数据面试题 Hadoop、kafka、HDFS、Spark、MapReduce 共19页.pdf

    18. **TOP K算法处理重复query**:可以使用MapReduce的Reduce阶段计算每个query的频率,然后在所有结果中找出频率最高的K个query。如果数据量大,可能需要多轮MapReduce作业或使用更高效的算法。 以上是针对2018年...

    十道海量数据处理面试题与十个方法大总结

    这是一个典型的 Top K 算法问题,解决方案是使用 Hash 表完成排序,然后使用堆结构找出 Top K。时间复杂度为 O(N) + N'*O(logK)。 三、有一个 1G 大小的一个文件,里面每一行是一个词,词的大小不超过 16 字节...

    基于项目k临近的协同过滤的Hadoop实现,数据集采用MovieLens.zip

    这一步可以通过排序和取Top-K操作来完成。 3. **预测评分**:基于找到的K个最近邻,利用加权平均或者其他方法预测目标电影的评分。预测公式通常为:预测评分 = ∑(sim(i,j) * r_ui) / ∑(sim(i,j)),其中sim(i,j)...

    分布式RDF关键词近似搜索方法.pdf

    通过分布式系统的技术支持,DKASR算法能够显著提升大规模RDF数据集上关键词搜索的效率与效果,最终实现高效、正确的关键词近似搜索并返回Top-k结果。 在文章中提及到的关键技术点和概念有: - RDF(资源描述框架)...

    十道海量数据处理面试题(卷).doc

    使用 Top-K 算法,例如可以使用堆结构(最小堆)存储前 100 个词及其频率,每次遇到新的词或词频更新时,根据堆的性质调整堆。这样可以保证堆顶总是频率最高的词。 3. 按 query 频度排序: 可以采用 MapReduce ...

    面试经验分享之机器学习、大数据问题(2).pdf

    - 如何在100亿数字中找出前100大的问题,可以使用分布式排序算法(如MapReduce的Top-K算法)。 9. **面试准备**: - 需要深入理解基础算法,并能对比不同算法的适用场景和优缺点。 - 掌握至少一种主流的大数据...

    海量数据查找数据问题

    通过选取合适的枢轴,可以在O(n)的时间复杂度内找到第k小(大)的元素,对于找中位数,我们只需找到第(n/2)小的元素即可。这种方法避免了全数组排序,大大提高了效率。 另一种方法是使用“二叉堆”或“最小堆”来...

    常见的海量数据处理方法

    为了进一步提高TOP-K算法的效率,可以采取以下策略: 1. **使用堆数据结构**:通过维护一个大小固定的堆来实时更新TOP-K列表。 2. **并行处理**:利用多核处理器的能力同时处理不同部分的数据。 3. **排序与筛选**...

    基于网格划分加权的分布式离群点检测算法.docx

    Hadoop MapReduce等框架被用来加速离群点检测,例如文献[18]提出的AVF方法适用于分类数据,而文献[19]的PKDTree适用于数值属性的大规模数据。文献[21]和[22]分别提出了分布式Top-n离群点检测和并行LOF计算,后者通过...

    mahout数据挖掘

    K-Means Mapper 在 MapReduce 框架中负责处理数据映射任务。它在初始化时读取上一次迭代产生的或初始的聚类中心。对于每个输入数据点,Mapper 计算其与所有聚类中心的距离,然后将其归入距离最近的聚类,并输出聚类 ...

    面试题目-大数据量海量数据处理.pdf

    2. **query频率排序**:可以使用哈希表统计每个query的出现次数,然后利用外部排序算法如K-way Merge排序这些频率数据。 3. **词频统计**:使用Trie树或倒排索引可以高效地统计词频,但内存限制需要分块处理,先...

    十道海量数据处理面试题(卷).docx

    在有限内存条件下,可以使用Top-K算法。首先读取文件的一部分,维护一个最小堆来存储出现频率最高的100个词,当堆满时,新词进来若比堆顶元素频率高,则替换掉堆顶元素。不断迭代此过程,最后堆中的词即为高频词。 ...

Global site tag (gtag.js) - Google Analytics