歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

Bit-map法處理大數據問題

問題引入:

1.給40億個不重復的unsigned int的整數,沒排過序的,然後再給一個數,如何快速判斷這個數是否在那40億個數當中?
2.給定一個千萬級別數據量的整數集合,判斷哪些是重復元素。
3.給定一個千萬級別數據量的整形數組,對其進行排序。
4.在5億個整數中找出不重復的整數(注意,內存不足以容納這5億個整數)。

從數據量上看,使用常規的解法(普通排序算法,逐個比較等)明顯不合適,所以這裡我們引入一個新的解法,就是Bitmap。

Bitmap就是用一個bit位來標記某個元素對應的Value, 而Key即是該bit的位序。由於采用了Bit為單位來存儲數據,因此可以大大節省存儲空間。 bitmap通過1個位表示一個狀態,比如:int類型有2^32個數字,即4G個數字,那麼每個數字一個狀態,就是2^32個bit,即512 MB(也就是說,用512兆存儲空間就可以處理4G個數據,即40+億數據)。

下面是我用C++寫的一個bitmap類,可以通過構造對象時傳入數據規模,動態申請所需的內存,然後處理用戶的大量數據:

#include<iostream>
#include<fstream>
#include<ctime>
using namespace std;
const unsigned SIZE = 512000000;//512兆靜態存儲區可處理40.96億數據

class Bitmap {
    typedef struct Byte {
        unsigned char bit8;
        static const unsigned char mask[9];//用來取得一個字節每一位的輔助數組
        Byte()
        {
            bit8 = 0;
        }
        //設置該位,就是存儲該數
        void set1(unsigned at)
        {
            bit8 |= mask[at];
        }
        //讀取該位是否有數
        bool get1(unsigned at)
        {
            return bit8 & mask[at];
        }
    } Byte;
    Byte *m_byte;
    unsigned m_size;
public:
    Bitmap(unsigned _size)
    {
        m_byte = new Byte[(_size+7)/8];
        m_size = _size;
    }
    virtual ~Bitmap()
    {
        delete[] m_byte;
        m_size = 0;
    }
    //存儲一個數據
    bool push(unsigned data)
    {
        if(data>=m_size)
            return false;
        m_byte[data/8].set1(data%8);
        return true;
    }
    //讀取一個數據是否存在
    bool find(unsigned data)
    {
        return data>=m_size ? 0 : m_byte[data/8].get1(data%8);
    }
    //返回能存儲的數據個數
    unsigned size()
    {
        return m_size;
    }
    //重載運算符實現常用功能
    //存儲一個數據
    bool operator>>(unsigned data)
    {
        return push(data);
    }
    //讀取一個數據是否存在
    bool operator<<(unsigned data)
    {
        return find(data);
    }
    //訪問到某個數據塊
    Byte& operator[](unsigned i)
    {
        if(i>=m_size/8)
            throw "index out of range";
        return m_byte[i];
    }
};
const unsigned char Bitmap::Byte::mask[9] = {0x80,0x40,0x20,0x10,0x8,0x4,0x2,0x1};//用來取得一個字節每一位的輔助數組

int main()
{
    Bitmap bitmap(8*SIZE);//可以存儲40+億數據
    ifstream file("in.txt");//從文件內錄入一些整數
    unsigned read, i=0, t1 = clock();
    for(i=0; i<SIZE; ++i)
        if(file>>read)
            bitmap>>read;
        else
            break;
    file.close();
    cout<<"共存儲"<<i/10000<<"W 數據, "<<"耗時: "<<clock()-t1<<"ms"<<endl;
    t1 = clock();
    for(i=0; i<1000000; ++i)
        if(bitmap<<i)
            ;
    cout<<"訪問"<<i/10000<<"W 數據共耗時: "<<clock()-t1<<"ms"<<endl;
    cout<<"請輸入需要檢索的數據:"<<endl;
    while(cin>>read) {
        if(bitmap<<read)
            cout<<"已存儲"<<read<<endl;
        else
            cout<<"Error: 未存儲"<<read<<endl;
    }
    return 0;
}

運行結果如下:

在程序中,先讀取一個文本文件中隨機產生的6W個整數,存到這個bitmap中,然後測試了一下從這個建立好的bitmap中查找100W數據耗時情況(11ms左右),接下來的部分是用戶可以手動輸入一些整數,程序會自動檢索bitmap中是否已存儲該數據。

這樣就可以解決引入話題中的第一個問題了,把輸入的文本數據改為已知的40億數據就可以了(40億數據的錄入可能需要一會兒,大概1300秒)。

下面給出引入的剩余三個問題的解題思路。

問題2:先建立一個足夠大的Bitmap對象,然後依次錄入這些數據,如果錄入某數據前發現該位已經為1,則該數據重復,依次得到重復的數據即可。

問題3:先建立一個足夠大的Bitmap對象,然後依次錄入這些數據,從Bitmap開始位置起遍歷,如果某位不為0,則表示有該數據,依次輸出不為0的位的位序就是排序好的數組(輸出太多沒意義,可以將輸出轉換到寫入文件,那麼新文件中數據就是排序好的)。

問題4:方法1,建立2個足夠大的Bitmap對象,依次錄入數據,錄入前先判斷該數據在bitmap1中是否存在(即對應位是否為1),不存在則錄入到bitmap1中,存在就錄入到bitmap2中;全部錄入完後,依次遍歷bitmap1中每一位,如果某一位為1但是bitmap2中對應位不為1,則表示該數據只出現過一次,依次輸出即可。

方法2,建立一個足夠大的Bitmap對象,不過用兩位表示一個數據,00表示數據不存在,01數據出現一次,10表示數據出現多次。11呢?一邊涼快去吧,不要你了,哈哈。這樣依次錄入數據時,如果該對應位(其實是兩位)為00則改為01,01就改為10,10就不管了。錄入完成後,遍歷整個bitmap,找到01位就輸出。

  好了,常見的大數據題目就通過bitmap這個神奇的結構給解決了,不過bitmap也不是萬能的,很明顯,它暫時只適合存儲整形數據,當然這裡只考慮了unsigned類型數據,如果是int類型的話,對應映射一下就可以了也是沒問題的。不過即使如此,也只能處理10億級別的數據,如果數據量更大、類型不只是整形呢?

  比如:需要寫一個網絡蜘蛛(web crawler)。由於網絡間的鏈接錯綜復雜,蜘蛛在網絡間爬行很可能會形成“環”。為了避免形成“環”,就需要知道蜘蛛已經訪問過哪那些URL。給一個URL,怎樣知道蜘蛛是否已經訪問過?

  不難想到如下幾種方案:

  1. 將訪問過的URL全部保存到數據庫;

  2. 用HashSet將訪問過的URL保存起來。那只需接近O(1)的代價就可以查到一個URL是否被訪問過;

  3. URL經過MD5或SHA-1等單向哈希後再保存到HashSet或數據庫。

  4. Bit-Map方法。建立一個BitSet,將每個URL經過一個哈希函數映射到某一位。

  方法1~3都是將訪問過的URL完整保存,方法4則只標記URL的一個映射位。

  以上方法在數據量較小的情況下都能完美解決問題,但是當數據量變得非常龐大時問題就來了。

  方法1:數據量變得非常龐大後關系型數據庫查詢的效率會變得很低。而且每來一個URL就啟動一次數據庫查詢是不是太小題大做了?

  方法2:太消耗內存。隨著URL的增多,占用的內存會越來越多。就算只有1億個URL,每個URL只算50個字符,就需要5GB內存。

  方法3:由於字符串經過MD5處理後的信息摘要長度只有128Bit,SHA-1處理後也只有160Bit,因此方法3比方法2節省了好幾倍的內存。

  方法4:消耗內存是相對較少的,但缺點是單一哈希函數發生沖突的概率太高。還記得數據結構課上學過的Hash表沖突的各種解決方法麼?若要降低沖突發生的概率到1%,就要將BitSet的長度設置為URL個數的100倍。

  但是我們可以考慮如果在一定程度上忽略誤判的情況,那麼是不是可以通過改進方法4實現這一功能?其實這就是Bloom Filter的算法 的思想:Bloom Filter是由Bloom在1970年提出的一種多哈希函數映射的快速查找算法。通常應用在一些需要快速判斷某個元素是否屬於集合,但是並不嚴格要求100%正確的場合。其思想就是在方法4基礎上做了一些改進,不是映射到一位,而是通過K個哈希函數映射到K位上,這樣只有當新的URL計算得到的K位都為1時才判斷為該URL已經訪問過(有誤判的可能性,不過有相關研究證明,取得合適的K值和bitmap位數時可以讓誤判率很小以至於可以忽略,參見細節)

  當然,還可以通過map-reduce來處理,畢竟人家mapreduce可是行家,專業的大數據處理技術嘛!

Copyright © Linux教程網 All Rights Reserved