數據算法第三章中的問題你面試和工作中遇到過嗎？
- 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，作者是冷夢顏愛楠楠。我後面會把這本書中的精華總結出來，供大家參考。
