数据算法第三章中的问题你面试和工作中遇到过吗？
- 2020 年 2 月 18 日
- 筆記
这个章节说起来非常简单，就是用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实现，这里就不写了。
这本书大家可以找找PDF，上面的一些思想真的很好，里面的一些场景无论是面试还是真实的业务场景都会遇到。
网上也有同学写了一些本书的读书笔记https://dwz.cn/0GhtboRq，作者是冷梦颜爱楠楠。我后面会把这本书中的精华总结出来，供大家参考。
