成都創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括莫力達(dá)網(wǎng)站建設(shè)、莫力達(dá)網(wǎng)站制作、莫力達(dá)網(wǎng)頁(yè)制作以及莫力達(dá)網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，莫力達(dá)網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到莫力達(dá)省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

位圖的概念：

    在C++中，位圖是以位來(lái)表示整數(shù)的結(jié)構(gòu)，普通的整數(shù)一個(gè)數(shù)需要用4個(gè)字節(jié)來(lái)表示，我們可以換種思想，在整個(gè)整數(shù)的集合范圍內(nèi)，某個(gè)整數(shù)存在與否，只有兩種情況，在或者不在，那么，我們可以考慮只用一個(gè)bit位，來(lái)表示該整數(shù)存在的狀態(tài)，從而達(dá)到節(jié)省內(nèi)存的目的。

位圖實(shí)例分析：

    給一個(gè)實(shí)際的例子，給40億個(gè)不重復(fù)的unsigned int的整數(shù)，沒(méi)排過(guò)序的，然后再給一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中

    我們可以簡(jiǎn)單計(jì)算一下，40億個(gè)整數(shù)全部放到內(nèi)存，需要160億個(gè)字節(jié)，粗略計(jì)算，大致需要16G的內(nèi)存，如果我們把每個(gè)整數(shù)是否出現(xiàn)，轉(zhuǎn)換成用一位來(lái)表示它存在的狀態(tài)，需要5億個(gè)字節(jié)，也就是大約500M的內(nèi)存，對(duì)于計(jì)算機(jī)而言，對(duì)內(nèi)存的節(jié)省亦常地重要，這就是位圖的一個(gè)重要應(yīng)用。

位圖模擬實(shí)現(xiàn)：

    首先我們考慮位圖的結(jié)構(gòu)，實(shí)際上也是對(duì)數(shù)組的封裝，只不過(guò)我們這里需要的是以bit位為單位進(jìn)行存放，每一位的狀態(tài)只有0和1兩種，這里用來(lái)表示該整數(shù)是否在位圖內(nèi)。

    我們以一個(gè)×××為例，在一個(gè)×××的空間，存儲(chǔ)【1 6 9 4 12 10】這些數(shù)，存儲(chǔ)結(jié)果應(yīng)該如下：

    這個(gè)只給出了兩個(gè)字節(jié)，全可以表示上面的6個(gè)整數(shù)。

    關(guān)于位圖的底層，這里我們使用vector來(lái)模擬實(shí)現(xiàn)。

#include <vector>
#include<iostream>
using namespace std;
class BitMap
{
public:
    BitMap(const size_t& range)
    {
        int sz = (range >> 5) + 1;
        _vec.resize(sz);
    }
    void BitSet(const size_t& x)
    {
        int index = x >> 5; // index是x對(duì)應(yīng)位所在的下標(biāo)
        int num = x % 32; // num是x對(duì)應(yīng)該×××的第多少位
        _vec[index] |= 1 << num;
    }
    void BitReSet(const size_t& x)
    {
        int index = x >> 5; // index是x對(duì)應(yīng)位所在的下標(biāo)
        int num = x % 32; // num是x對(duì)應(yīng)該×××的第多少位
        _vec[index] &= (~(1 << num));
    }
    bool BitTest(const size_t& x)
    {
        int index = x >> 5; // index是x對(duì)應(yīng)位所在的下標(biāo)
        int num = x % 32; // num是x對(duì)應(yīng)該×××的第多少位
        return _vec[index] & (1 << num);
    }
protected:
    vector<int> _vec;
};

    位圖的實(shí)現(xiàn)實(shí)際上就是進(jìn)行一系列的位操作，通過(guò)位操作找到該×××對(duì)應(yīng)的位，下面給出一組簡(jiǎn)單的測(cè)試用例
    

void TestBitMap()
{
    BitMap  mp(100);
    mp.BitSet(1);
    mp.BitSet(2);
    mp.BitSet(11);
    mp.BitSet(22);
    cout << "test --<1>" << mp.BitTest(1) << endl;
    cout << "test --<2>" << mp.BitTest(2) << endl;
    cout << "test --<11>" << mp.BitTest(11) << endl;
    cout << "test --<22>" << mp.BitTest(22) << endl<<endl;
    mp.BitReSet(2);
    cout << "test --<1>" << mp.BitTest(1) << endl;
    cout << "test --<2>" << mp.BitTest(2) << endl;
    cout << "test --<11>" << mp.BitTest(11) << endl;
    cout << "test --<22>" << mp.BitTest(22) << endl << endl;
}

    

源碼庫(kù)中的位圖：

    在源碼庫(kù)中，有這樣一個(gè)容器 bitset，和我們這里的bitmap性質(zhì)基本是一樣的，當(dāng)然，功能要比上面實(shí)現(xiàn)的位圖大得多。

A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1, true or false, ...).

The class is very similar to a regular array, but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).

Each element (each bit) can be accessed individually: for example, for a given bitset named mybitset, the expression mybitset[3] accesses its fourth bit, just like a regular array accesses its elements.

Because no such small elemental type exists in most C++ environments, the individual elements are accessed as special references which mimic bool elements:

    庫(kù)中提供了一系列的函數(shù)操作，除了set、reset、test之外，常用的還有filp<取反操作>，count<統(tǒng)計(jì)位為1的個(gè)數(shù)>。關(guān)于bitset的操作，都包含在

#include <bitset>

的頭文件中。

    

位圖的分析與擴(kuò)展：

    位圖的確用起來(lái)會(huì)很方便，但并不是任何情況下都需要使用到位圖的，位圖通常是為了處理大量數(shù)據(jù)，內(nèi)存中不足以存放所有的數(shù)字才使用的一種數(shù)據(jù)結(jié)構(gòu)，因?yàn)槲粓D也有著一定的缺陷：

    1> 它的可讀性差

    2> 位圖在視圖節(jié)約空間的時(shí)候，也伴隨著一定的消耗，它要求給最大值和最小值之間的所有數(shù)都要占用一個(gè)bit位，當(dāng)數(shù)據(jù)過(guò)于分散而數(shù)據(jù)量又不至太大的情況，位圖其實(shí)是一種比較浪費(fèi)空間的做法。如果最小值為10000，位圖開(kāi)辟出來(lái)的前10000個(gè)bit位其實(shí)就空了出來(lái)，沒(méi)有利用到，之前我們舉得例子，40億個(gè)整數(shù)，因?yàn)闊o(wú)符號(hào)整數(shù)的最大值就到42.9億左右，大部分的整數(shù)值確定都已經(jīng)被取到，因此我們采用了位圖來(lái)實(shí)現(xiàn)。

    3> 當(dāng)位圖用來(lái)存儲(chǔ)有符號(hào)整數(shù)時(shí)，有兩種解決方案，一種是我們約定好最小值不再?gòu)?開(kāi)始，所有的計(jì)算都需要減去有符號(hào)整數(shù)的最大值，另一種是這里采用兩位來(lái)存儲(chǔ)一個(gè)數(shù)，用兩位來(lái)表示正數(shù)、負(fù)數(shù)、不存在三種狀態(tài)。

    試想，如果我們要求統(tǒng)計(jì)40億個(gè)無(wú)符號(hào)整數(shù)中，出現(xiàn)兩次以上的數(shù)該如何處理？

。。。。。。

    同樣，多加一位標(biāo)志位，用兩個(gè)bit位來(lái)進(jìn)行處理，那這樣的話，就需要我們自己來(lái)實(shí)現(xiàn)一個(gè)基本的兩位為一個(gè)單元的位圖結(jié)構(gòu)。

    除此之外，位圖還可用來(lái)排序，判重，當(dāng)然這里僅僅限于無(wú)符號(hào)整數(shù)，和上一節(jié)的哈希一樣，受限于整數(shù)范圍確實(shí)是個(gè)不好的地方，下一談會(huì)提到字符串哈希算法與布隆過(guò)濾器，正是由于字符串哈希算法，才使得這些數(shù)據(jù)結(jié)構(gòu)得以大范圍的使用。

關(guān)于哈希算法：
    http://muhuizz.blog.51cto.com/11321490/1870717

                            -----muhuizz整理

當(dāng)前題目：海量數(shù)據(jù)處理第二談-----位圖BitMap
分享鏈接：http://jinyejixie.com/article22/ghopcc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開(kāi)發(fā)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站營(yíng)銷、品牌網(wǎng)站制作、微信公眾號(hào)、品牌網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)