數據演算法第三章中的問題你面試和工作中遇到過嗎?

  • 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,作者是冷夢顏愛楠楠。我後面會把這本書中的精華總結出來,供大家參考。