今天去百度面试,这么简单的题做法都有问题,悲哀啊,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);
}
}
相关推荐
5. **相似度计算**:在Reduce阶段,我们计算每对物品的相似度,这一步可能涉及到一些优化技巧,如采样或者Top-K策略,以减少计算量。 6. **推荐生成**:最后,对于每个用户,我们找出其已评分物品的相似物品,并...
内容涵盖HDFS的JAVA API操作,如文件读取、写入、删除、元数据查询和文件列表等,以及MapReduce编程模型的多个应用,包括求平均数、Join操作、TopK算法、二次排序,并涉及自定义InputFormat、OutputFormat和shuflle...
本文的创新之处在于将Top-k天际线计算与MapReduce框架相结合,设计了一种新颖的算法。之前的研究存在的问题包括I/O开销大、缺乏进步性(即逐步剔除非支配数据点的能力)、以及集中式分布而非分布式。而MR-DTKS算法的...
### MapReduce环境下面向用户偏好的top-k连接查询处理方法 #### 一、研究背景与意义 随着互联网技术的快速发展和大数据时代的到来,如何高效地处理海量数据成为了研究的热点。传统的数据库管理系统难以应对大数据...
此外,论文还探讨了一种基于项目层次结构相似性的推荐算法,这种方法利用层次结构来度量项目间的相似度,并结合最短路径算法Dijkstra和TopK思想找到最相关的项目。通过与其他算法的对比,展示了其在某些场景下的优势...
10. **Top K问题**:最小堆可以实时维护K个最小元素,适用于在线问题。最大堆配合反序操作可用于找到最大的K个元素。空间允许时,还可以一次性将所有元素放入数组,使用快速选择或堆排序。 11. **位图(Bitmap)**...
目录 第1章二次排序:简介 19 第2章二次排序:详细示例 42 第3章 Top 10 列表 54 第4章左外连接 96 第5章反转排序 127 第6章移动平均 137 第7章购物篮分析 155 第8章共同好友 182 第9章使用MapReduce实现推荐引擎 ...
18. **TOP K算法处理重复query**:可以使用MapReduce的Reduce阶段计算每个query的频率,然后在所有结果中找出频率最高的K个query。如果数据量大,可能需要多轮MapReduce作业或使用更高效的算法。 以上是针对2018年...
这是一个典型的 Top K 算法问题,解决方案是使用 Hash 表完成排序,然后使用堆结构找出 Top K。时间复杂度为 O(N) + N'*O(logK)。 三、有一个 1G 大小的一个文件,里面每一行是一个词,词的大小不超过 16 字节...
这一步可以通过排序和取Top-K操作来完成。 3. **预测评分**:基于找到的K个最近邻,利用加权平均或者其他方法预测目标电影的评分。预测公式通常为:预测评分 = ∑(sim(i,j) * r_ui) / ∑(sim(i,j)),其中sim(i,j)...
通过分布式系统的技术支持,DKASR算法能够显著提升大规模RDF数据集上关键词搜索的效率与效果,最终实现高效、正确的关键词近似搜索并返回Top-k结果。 在文章中提及到的关键技术点和概念有: - RDF(资源描述框架)...
使用 Top-K 算法,例如可以使用堆结构(最小堆)存储前 100 个词及其频率,每次遇到新的词或词频更新时,根据堆的性质调整堆。这样可以保证堆顶总是频率最高的词。 3. 按 query 频度排序: 可以采用 MapReduce ...
- 如何在100亿数字中找出前100大的问题,可以使用分布式排序算法(如MapReduce的Top-K算法)。 9. **面试准备**: - 需要深入理解基础算法,并能对比不同算法的适用场景和优缺点。 - 掌握至少一种主流的大数据...
通过选取合适的枢轴,可以在O(n)的时间复杂度内找到第k小(大)的元素,对于找中位数,我们只需找到第(n/2)小的元素即可。这种方法避免了全数组排序,大大提高了效率。 另一种方法是使用“二叉堆”或“最小堆”来...
为了进一步提高TOP-K算法的效率,可以采取以下策略: 1. **使用堆数据结构**:通过维护一个大小固定的堆来实时更新TOP-K列表。 2. **并行处理**:利用多核处理器的能力同时处理不同部分的数据。 3. **排序与筛选**...
Hadoop MapReduce等框架被用来加速离群点检测,例如文献[18]提出的AVF方法适用于分类数据,而文献[19]的PKDTree适用于数值属性的大规模数据。文献[21]和[22]分别提出了分布式Top-n离群点检测和并行LOF计算,后者通过...
K-Means Mapper 在 MapReduce 框架中负责处理数据映射任务。它在初始化时读取上一次迭代产生的或初始的聚类中心。对于每个输入数据点,Mapper 计算其与所有聚类中心的距离,然后将其归入距离最近的聚类,并输出聚类 ...
2. **query频率排序**:可以使用哈希表统计每个query的出现次数,然后利用外部排序算法如K-way Merge排序这些频率数据。 3. **词频统计**:使用Trie树或倒排索引可以高效地统计词频,但内存限制需要分块处理,先...
在有限内存条件下,可以使用Top-K算法。首先读取文件的一部分,维护一个最小堆来存储出现频率最高的100个词,当堆满时,新词进来若比堆顶元素频率高,则替换掉堆顶元素。不断迭代此过程,最后堆中的词即为高频词。 ...