面试字节跳动被问到这个问题:如何用Hadoop或者Spark来解决TopN

这个章节说起来非常简单，就是用Hadoop或者Spark来解决TopN。

这个章节详细的提出了几种方法解决这个问题。我们来看一下，直接上答案。

• 假设输入键都是唯一的，也即给定的输入集合{(K,V)},所有的K都是唯一的，用Mapreduce/Hadoop方法
• 假设输入键都是唯一的，也即给定的输入集合{(K,V)},所有的K都是唯一的，用spark方法
• 假设输入键都不是唯一的，也即给定的输入集合{(K,V)},K是有重复的，用spark强大的排序算法top()函数和takeOrdered()等

Java计算TopN

Java中实现Top N的方法最常用的是适用SortedMap<K,V>和TreeMap<K,V>,然后将L的所有元素增加到topN中，如果topN.size()>N,则删除第一个元素或最后一个元素。

基于MapReduce实现的键唯一方法

重写setup和cleanup函数，这里两个函数在每次启动映射器都会执行一次，setup用于获取N的值，cleanup用于发射每个映射器的TOP N到reduce端。

Map函数，完成分区的TopN求值

Reduce函数，完成所有的TopN求值

驱动程序类TopNDriver.java

查找Top 10 和 Bottom 10

基于Spark实现的键唯一方法

Java API使用的spark函数类

在spark中使用setUp()和cleanUp()

采用spark实现TopN

全局指定TopN 参数

• 定义broadcastTopN：final Broadcast<Integer> broadcastTopN = context.broadcast(topN)
• 获取N的值：final int topN = broadcastTopN.value();

基于Spark实现的键不唯一的方法

算法过程

• 要保证K是唯一的，要把输入映射到JavaPairRDD<K,V>对，然后交给reduceByKey()
• 将所有唯一的(K,V)对划分为M个分区
• 找到各个分区的TopN （本地TopN）
• 找出所有本地TopN的最终TopN

基于Spark实现的非唯一键方法

基于takeOrdered实现的键不唯一的方法

当然你还可以使用scala实现，这里就不写了。