我們平時(shí)很容易遇到說(shuō)排序，并取前N個(gè)的狀況。
我們根據(jù)數(shù)據(jù)類(lèi)型可以簡(jiǎn)單分為重復(fù)鍵和不重復(fù)鍵的topN
MapReduce
對(duì)于MR來(lái)說(shuō)综看，topN代碼比較多一些脾拆，在這里我只講講思路馒索。
當(dāng)無(wú)重復(fù)鍵的時(shí)候，
我們有數(shù)據(jù)("w"->2,"ww"->3,"r"->3)
我們的目的是對(duì)值進(jìn)行排序名船，如用戶(hù)點(diǎn)擊了幾次網(wǎng)頁(yè)绰上，值記錄的就是網(wǎng)頁(yè)。
map階段渠驼，我們要做的是獲取并且處理數(shù)據(jù)蜈块，并完成本地的topN排序。
在排序時(shí)我們用的是java自帶的treeMap(它是一個(gè)基于紅黑樹(shù)的實(shí)現(xiàn))迷扇。
為什么要在map階段就進(jìn)行排序呢百揭？
因?yàn)樵跀?shù)據(jù)量巨大的時(shí)候，為了減少RPC和reduce的壓力谋梭。于是我們?cè)趍ap排好序并篩選出前N個(gè)信峻。
reduce階段，我們只需要把map傳來(lái)的topN再進(jìn)行一次排序篩選出前N個(gè)瓮床。
這樣我們的目的就達(dá)成了盹舞。
對(duì)于非唯一鍵，MR顯得笨拙一些隘庄，它必須先經(jīng)過(guò)一次reduce踢步，把非唯一鍵變成唯一鍵后再重復(fù)上述操作。
spark
spark具有高層抽象函數(shù)丑掺。所以排序顯得十分簡(jiǎn)單街州。在這里主要看看這幾個(gè)函數(shù)。
sortby
def sortBy[S](f: JFunction[T, S], ascending: Boolean, numPartitions: Int): JavaRDD[T]
sortby函數(shù)可以完成對(duì)指定數(shù)據(jù)的排序黍翎，(k,v)既可以指定k也可以指定v匣掸，第二個(gè)參數(shù)是選擇正序還是逆序（默認(rèn)是true正序，一般要topN的話用逆序）送爸，因?yàn)檫@是一個(gè)shuffle操作所以可要指定分區(qū)碱璃。sortbykey
比sortby少一個(gè)第一個(gè)參數(shù)，它是僅對(duì)key的排序肛真。sortwith
def sortWith(lt: (A, A) => Boolean): Repr = sorted(Ordering fromLessThan lt)
一種自定義排序的方法takeOrder
take
def take(num: Int): Array[T]
抽取rdd的前n個(gè)元素top
def top(num: Int)(implicit ord: Ordering[T]): Array[T]
默認(rèn)使用降序乾忱，并抽取前n個(gè)元素tabkeOrdered
def takeOrdered(num: Int)(implicit ord: Ordering[T]): Array[T]
默認(rèn)使用升序窄瘟，并抽取前n個(gè)元素
val arr=Map(1->2,2->3,3->1,4->4,4->5,10->23,12->21,10->2,9->1,0->2,9->3)
val conf=new SparkConf().setAppName("test")
val sc=new SparkContext(conf)
val rdd=sc.parallelize(arr.toList,4)
println(rdd.partitions.size+"======================================")
val rerdd=rdd.coalesce(3)
println((rerdd.partitions.size+"======================================"))
val pairs=rerdd.map(x=>new Tuple2(x._1,x._2))
val result=pairs.reduceByKey(_+_)
println(result.partitions.size+"======================================")
val partitions=result.sortBy(x=>x._2,false)
val res=partitions.take(3)
res.foreach(x=>println(x))
代碼的簡(jiǎn)單實(shí)現(xiàn)锄列。
思考：如果大量數(shù)據(jù)中進(jìn)行topN有什么優(yōu)化呢邻邮？
個(gè)人認(rèn)為剪枝是必要的筒严，假如對(duì)于1-100分布的數(shù)服從正態(tài)分布，我們自然就可以過(guò)濾掉百分之50-70的數(shù)。
如果在已知平均值等情況下睬塌，更方便進(jìn)行剪枝勋陪。
