一、二次排序問題。

　　　　　　　　　　　　　　　　　　　　　　

　　MR/hadoop兩種方案：

　　　　1.讓reducer讀取和緩存給個(gè)定鍵的所有值（例如，緩存到一個(gè)數(shù)組數(shù)據(jù)結(jié)構(gòu)中，）然后對(duì)這些值完成一個(gè)reducer中排序。這種方法不具有可伸縮性，因?yàn)閞educer要接受一個(gè)給定鍵的所有值，這種方法可能導(dǎo)致reducer的內(nèi)存耗盡（OOM）。另一方面，如果值數(shù)量很少，就不會(huì)導(dǎo)致內(nèi)存溢出，那么這種方法可行。

　　　　2.使用MR框架對(duì)reducer的值排序（這樣一來，就不再需要對(duì)傳入reducer的值完成排序。）這種方法“會(huì)為自然鍵增加部分或整個(gè)值來創(chuàng)建一個(gè)組合鍵以實(shí)現(xiàn)排序目標(biāo)”（參考 java Code Geeks）。這種方法可伸縮，不會(huì)產(chǎn)生內(nèi)存溢出錯(cuò)誤。在這里，排序工作基本上由MR框架來完成。

　　　　? ?使用MR框架的二次排序設(shè)計(jì)模式，規(guī)約器值到達(dá)時(shí)就是有序地。（也就是說，不再需要在內(nèi)存中對(duì)值進(jìn)行排序）。這種技術(shù)使用了MR框架的洗牌和排序技術(shù)完成規(guī)約器值的排序。這種解決方案比1更可取，不再依賴內(nèi)存完成排序?！　　　?/p>

　　　　思考分析：對(duì)返回?cái)?shù)據(jù)形式進(jìn)行分析，自定義對(duì)象和reducer的分區(qū)策略。（當(dāng)然為了實(shí)現(xiàn)排序，要對(duì)自定義的對(duì)象進(jìn)行實(shí)現(xiàn)comparele接口，重寫compare方法。）

?

　　spark兩種方案：

　　　　1.將一個(gè)給定鍵的所有值讀取緩存到一個(gè)List數(shù)組結(jié)構(gòu)中，然后對(duì)這些值完成排序。優(yōu)缺點(diǎn)同MR方案1.

　　　　2.使用Spark框架對(duì)規(guī)約器值排序（這種做法不需要對(duì)傳入規(guī)約器的值完成規(guī)約器中排序）。這種方法“會(huì)為自然建增加部分或整個(gè)值來創(chuàng)建一個(gè)組合鍵以實(shí)現(xiàn)排序目標(biāo)?！?/p>

?

二。 Top N問題。

　　列表L的TopN 算法大致描述：L列表的元素是一個(gè)scala的tuple結(jié)構(gòu)，通過java的TreeMap將一個(gè)tuple添加到其中，然后對(duì)TreeMap進(jìn)>N的if操作，來進(jìn)行remove操作。

　　1.唯一鍵。

　　　　例子：

　　　　　　　　

　　　　在這個(gè)問題上，可以使用一個(gè)規(guī)約器完成對(duì)所有數(shù)據(jù)的接收，所有壓力和負(fù)載全部是都在這一個(gè)節(jié)點(diǎn)上。在這里不糊帶來性能問題，為什么呢。假設(shè)有由1000個(gè)映射，每個(gè)映射器只會(huì)生成10個(gè)鍵值對(duì)，因?yàn)?#xff0c;這個(gè)規(guī)約器只會(huì)得到10*1000個(gè)記錄，這個(gè)數(shù)據(jù)量還不至于導(dǎo)致性能瓶頸。

　　　　　　　　　　　　　　　　　　　　　　

　　　　2.非唯一鍵

?　　　　　　例子：

　　　　　　　　

　　　　　　topN設(shè)計(jì)模式：這里假設(shè)所有K不是唯一的，主要步驟：

　　　　　　　?、?。確保所有K是唯一的。要保證K是唯一的(存在不唯一的，直接把相同的K的V相加。)，我們要把輸入映射到JavaPairRDD<K,V>對(duì)，然后交給reduceByKey().

　　　　　　　?、?。將所有唯一的（K，V）對(duì)劃分為M個(gè)分區(qū)。

　　　　　　　?、?。找出個(gè)個(gè)分區(qū)的Top N。

　　　　　　　?、?。找出所有本地topN的最終top N.

　　　　　　

　　　　　　

轉(zhuǎn)載于:https://www.cnblogs.com/dhName/p/11351718.html

總結(jié)

以上是生活随笔為你收集整理的数据算法 --hadoop/spark数据处理技巧 --（二次排序问题和TopN问题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。