C++算法之海量數據處理方法的總結分析

2020-01-26 16:04:17

字體：大中小

來源：轉載

供稿：網友

海量數據處理中常用到的技術
1. Bloom Filtering
基本的Bloom Filtering支持快速的插入和查找操作，是一種hash表技術。基本的數據結構非常簡單，容量為m的位數組，k個hash函數，將輸入的n個元素存儲在位數組里面。
每次插入一個新的元素，先計算該元素的k個hash指，將位數組對應hash值位置為1. 查找某個元素時，同樣的先計算k個hash值，然后查詢看是否對應位數組中得k位是否都是1，是則斷定元素存在。
基本的Bloom Filtering算法可以用于允許誤差的快速判重操作。集合的交集、并集的計算。
Bloom Filtering有個改進的版本counting bloom filtering可以支持數據的刪除操作，countering bloom filtering和基本的bloom filtering相比，位數組中每一位的取值擴展成多位，基本的bloom filtering用1bit表示一位。插入一個元素時，所有的k位都加1，刪除時都減1，查找時如果k個值都大于0則判定為存在。CBF中有個很重要的參數，即每一位的位數為多少?？梢酝ㄟ^理論證明，位數一般取4就足夠了，可以支持同一個數據插入16次。
bitmap可以看做bloom filtering的特例
2. Hash表技術
d-left hash hash表負載均衡技術。將hash表分成d段，設計d個hash函數，更具負載選擇一個合適的段存放數據。查找時要計算d個hash值，分別在d段中找。
常用于統計次數。
3. 堆技術
堆有兩個典型的應用：
多路歸并排序
求TopK
多路歸并排序時，降序排序時用最大堆，升序排序用最小堆。
TopK時，求TopK最大時，用最小堆，求TopK最小時用最大堆。求topK最大時，利用最小堆堆維護K個值，當新掃描的值大于堆頂元素時，堆頂元素刪除，插入新的值。這樣掃描完一遍數據，既可以求得topK最大。
4. 雙層桶（多層桶）設計
hash表技術是一種direct addr 技術，但是當數據范圍分布過廣、且數據量非常大的時候，采用hash表直接direct addr技術就不行了，這是可以使用多層hash技術。將原始數據范圍分成小段，每一段內存可以裝載，段內可以使用direct addr table技術。可以用多層分級快速定位到小段。

上一篇：探討C++中數組名與指針的用法比較分析

下一篇：海量數據處理系列之:用C++實現Bitmap算法