C++算法之海量數(shù)據(jù)處理方法的總結(jié)分析
海量數(shù)據(jù)處理中常用到的技術(shù)
1. Bloom Filtering
基本的Bloom Filtering支持快速的插入和查找操作,是一種hash表技術(shù)?;镜臄?shù)據(jù)結(jié)構(gòu)非常簡單,容量為m的位數(shù)組,k個hash函數(shù),將輸入的n個元素存儲在位數(shù)組里面。
每次插入一個新的元素,先計算該元素的k個hash指,將位數(shù)組對應(yīng)hash值位置為1. 查找某個元素時,同樣的先計算k個hash值,然后查詢看是否對應(yīng)位數(shù)組中得k位是否都是1,是則斷定元素存在。
基本的Bloom Filtering算法可以用于允許誤差的快速判重操作。集合的交集、并集的計算。
Bloom Filtering有個改進(jìn)的版本counting bloom filtering可以支持?jǐn)?shù)據(jù)的刪除操作,countering bloom filtering和基本的bloom filtering相比,位數(shù)組中每一位的取值擴(kuò)展成多位,基本的bloom filtering用1bit表示一位。插入一個元素時,所有的k位都加1,刪除時都減1,查找時如果k個值都大于0則判定為存在。CBF中有個很重要的參數(shù),即每一位的位數(shù)為多少??梢酝ㄟ^理論證明,位數(shù)一般取4就足夠了,可以支持同一個數(shù)據(jù)插入16次。
bitmap可以看做bloom filtering的特例
2. Hash表技術(shù)
d-left hash hash表負(fù)載均衡技術(shù)。將hash表分成d段,設(shè)計d個hash函數(shù),更具負(fù)載選擇一個合適的段存放數(shù)據(jù)。查找時要計算d個hash值,分別在d段中找。
常用于統(tǒng)計次數(shù)。
3. 堆技術(shù)
堆有兩個典型的應(yīng)用:
多路歸并排序
求TopK
多路歸并排序時,降序排序時用最大堆,升序排序用最小堆。
TopK時,求TopK最大時,用最小堆,求TopK最小時用最大堆。求topK最大時,利用最小堆堆維護(hù)K個值,當(dāng)新掃描的值大于堆頂元素時,堆頂元素刪除,插入新的值。這樣掃描完一遍數(shù)據(jù),既可以求得topK最大。
4. 雙層桶(多層桶)設(shè)計
hash表技術(shù)是一種direct addr 技術(shù),但是當(dāng)數(shù)據(jù)范圍分布過廣、且數(shù)據(jù)量非常大的時候,采用hash表直接direct addr技術(shù)就不行了,這是可以使用多層hash技術(shù)。將原始數(shù)據(jù)范圍分成小段,每一段內(nèi)存可以裝載,段內(nèi)可以使用direct addr table技術(shù)。可以用多層分級快速定位到小段。
上一篇:基于字符串移位包含的問題詳解
欄 目:C語言
本文標(biāo)題:C++算法之海量數(shù)據(jù)處理方法的總結(jié)分析
本文地址:http://mengdiqiu.com.cn/a1/Cyuyan/4410.html
您可能感興趣的文章
- 04-02c語言沒有round函數(shù) round c語言
- 01-10深入理解C++中常見的關(guān)鍵字含義
- 01-10使用C++實(shí)現(xiàn)全排列算法的方法詳解
- 01-10APUE筆記之:進(jìn)程環(huán)境詳解
- 01-10深入第K大數(shù)問題以及算法概要的詳解
- 01-10c++中inline的用法分析
- 01-10深入N皇后問題的兩個最高效算法的詳解
- 01-10用C++實(shí)現(xiàn)DBSCAN聚類算法
- 01-10深入全排列算法及其實(shí)現(xiàn)方法
- 01-10全排列算法的非遞歸實(shí)現(xiàn)與遞歸實(shí)現(xiàn)的方法(C++)


閱讀排行
本欄相關(guān)
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對數(shù)函數(shù)的表達(dá)式 c語言中對
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機(jī)閱讀
- 01-10SublimeText編譯C開發(fā)環(huán)境設(shè)置
- 01-11ajax實(shí)現(xiàn)頁面的局部加載
- 01-10C#中split用法實(shí)例總結(jié)
- 01-10使用C語言求解撲克牌的順子及n個骰子
- 08-05織夢dedecms什么時候用欄目交叉功能?
- 08-05DEDE織夢data目錄下的sessions文件夾有什
- 08-05dedecms(織夢)副欄目數(shù)量限制代碼修改
- 01-10delphi制作wav文件的方法
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文
- 04-02jquery與jsp,用jquery