一、處理方法

表格

二、經(jīng)典實(shí)例

1.top K問(wèn)題

方案：分治+Trie樹(shù)/hash+小頂堆

將數(shù)據(jù)集按照hash方法分成多個(gè)小數(shù)據(jù)集；

使用Trie樹(shù)/hash統(tǒng)計(jì)每個(gè)小數(shù)據(jù)集中的query詞頻；

用小頂堆求出每個(gè)數(shù)據(jù)集中出現(xiàn)頻率最高的前K個(gè)數(shù)；

在所有top K中求出最終的top K

注：

• 不能直接將數(shù)據(jù)劃分，應(yīng)按照hash方法劃分。
  • 直接的話(huà)可能會(huì)將1000個(gè)apple分到多個(gè)數(shù)據(jù)集中，在那些數(shù)據(jù)集中它不算是最多的，不會(huì)出現(xiàn)在小top K中，也就不會(huì)出現(xiàn)在最終的top K中

有1億個(gè)浮點(diǎn)數(shù)怎么找出其中最大的10000個(gè)？

方法1、將數(shù)據(jù)全部排序，在排序后的集合中找。

方法2、局部淘汰法。容器中保存前10000個(gè)數(shù)，后面的數(shù)一一與容器中的最小數(shù)進(jìn)行比較，若大則替換。

方法3、分治法。分成100份，找出每份中的最大的10000個(gè)，再在100*10000個(gè)中找最大的10000個(gè)。

方法4、hash法。若數(shù)據(jù)中由很多重復(fù)的數(shù)，先用hash法，去重，減少內(nèi)存量，用分治法或者最小堆法進(jìn)行查找。

方法5、最小堆法。讀入前10000個(gè)創(chuàng)建最小堆，后續(xù)數(shù)與最小堆對(duì)頂元素進(jìn)行比較。

可能的應(yīng)用場(chǎng)景：

1.單機(jī)+單核+足夠大內(nèi)存：方法1

2.單機(jī)+多核+足夠大內(nèi)存：方法3（劃分塊數(shù)可>核數(shù)，避免數(shù)據(jù)傾斜，一個(gè)處理完接著處理下一個(gè)）

3.單機(jī)+單核+受限內(nèi)存：方法2

4.多機(jī)+受限內(nèi)存：方法3（hash+Socket）

?

2.重復(fù)問(wèn)題

通過(guò)位圖法實(shí)現(xiàn)

每個(gè)數(shù)字對(duì)應(yīng)位圖中的一個(gè)bit位

?

3.排序問(wèn)題

方法1：數(shù)據(jù)庫(kù)排序法。

? ? ? ? 讓數(shù)據(jù)庫(kù)索引排序操作后提取文件到內(nèi)存

方法2：分治法。

? ? ? ? hash法將數(shù)據(jù)分段，編碼復(fù)雜，速度也慢

方法3：位圖法。

? ? ? ? 數(shù)組下標(biāo)表示數(shù)值，用數(shù)組元素的值0表示沒(méi)有這個(gè)數(shù)，1表示有這個(gè)數(shù)

?

?

?

?

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的宝典9.2——海量数据的基本处理方法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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