分治，分布式。BitMap(位圖)及其升級版bloom filter是處理海量數(shù)據(jù)常用的方法，這里先介紹BitMap概念及其c++實現(xiàn)。

一、BitMap位圖

該數(shù)據(jù)結(jié)構(gòu)描述了一個有限定義域內(nèi)的稠密集合，其中的每一個元素最多出現(xiàn)一次并且沒有其他任何數(shù)據(jù)與該元素相關(guān)聯(lián)。

即使這些條件沒有完全滿足（例如，存在重復(fù)元素或額外的數(shù)據(jù)），也可以用有限定義域內(nèi)的鍵作為一個表項更復(fù)雜的表格索引。

所謂的Bit-map就是用一個bit位來標(biāo)記某個元素對應(yīng)的Value， 而Key即是該元素。

由于采用了Bit為單位來存儲數(shù)據(jù)，因此在存儲空間方面，可以大大節(jié)省。

例如假設(shè)我們要對0-7內(nèi)的5個元素(4,7,2,5,3)排序（這里假設(shè)這些元素沒有重復(fù)）。

那么我們就可以采用Bit-map的方法來達(dá)到排序的目的。

要表示8個數(shù)，我們就只需要8個Bit（1Bytes），首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0，

如下圖：

遍歷第一個元素4，則在第4為標(biāo)1：

以此來推，遍歷完所有后結(jié)構(gòu)：

我們現(xiàn)在遍歷一遍Bit區(qū)域，將該位是bit 1的位的編號輸出（2，3，4，5，7），這樣就達(dá)到了排序的目的。

二、C++實現(xiàn)

我們可以用一個unsigned int類型的數(shù)組或者向量來表示位圖，假設(shè)我們定義vector<unsigned int> a，則 第i位可表示為a[i/32]的i%32位（其中，32*N+r = i，r為i%32，也就是i/32的余數(shù)）。

由于計算機(jī)對位的操作比乘除法更有效率，這里計算i/32可以用位移操作：i>>5；計算i%32可以用1&31。

若是一個char數(shù)組str，則str的第i位為i/8(i>>3)地址塊的第i%8(i&7)位.下面以char為例說明，int類比可知。

#include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;
class BitMap{
private:
        char *bitmap;
        int gsize;
public:
       BitMap(){
       gsize=(10000>>3)+1;//default 10000
       bitmap= new char[gsize];
       memset(bitmap,0,sizeof(bitmap));
                }
       BitMap(int n){
       gsize=(n>>3)+1;
       bitmap=new char[gsize];
       memset(bitmap,0,sizeof(bitmap));
                  }
       ~BitMap(){delete []bitmap;}
       int get(int x){
       int cur=x>>3;
       int red=x&7;
       if(cur>gsize)return -1;
       return (bitmap[cur]&=1>>red); 
                      }
       bool set(int x){
       int cur=x>>3;//獲取元素位置,除8得到哪個元素，x/2^3得到那一個byte 
       int red=x&(7);//邏輯與，獲取進(jìn)準(zhǔn)位置,x&7==x%8.該Byte里第幾個 
       if(cur>gsize)return 0;
       bitmap[cur]|=1>>red;//賦值，1向右移動red位，|表示該位賦值1
       return 1; 
                       }
};

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論