您好,登錄后才能下訂單哦!
位圖的概念:
在C++中,位圖是以位來表示整數(shù)的結(jié)構(gòu),普通的整數(shù)一個數(shù)需要用4個字節(jié)來表示,我們可以換種思想,在整個整數(shù)的集合范圍內(nèi),某個整數(shù)存在與否,只有兩種情況,在或者不在,那么,我們可以考慮只用一個bit位,來表示該整數(shù)存在的狀態(tài),從而達到節(jié)省內(nèi)存的目的。
位圖實例分析:
給一個實際的例子,給40億個不重復(fù)的unsigned int的整數(shù),沒排過序的,然后再給一個數(shù),如何快速判斷這個數(shù)是否在那40億個數(shù)當(dāng)中
我們可以簡單計算一下,40億個整數(shù)全部放到內(nèi)存,需要160億個字節(jié),粗略計算,大致需要16G的內(nèi)存,如果我們把每個整數(shù)是否出現(xiàn),轉(zhuǎn)換成用一位來表示它存在的狀態(tài),需要5億個字節(jié),也就是大約500M的內(nèi)存,對于計算機而言,對內(nèi)存的節(jié)省亦常地重要,這就是位圖的一個重要應(yīng)用。
位圖模擬實現(xiàn):
首先我們考慮位圖的結(jié)構(gòu),實際上也是對數(shù)組的封裝,只不過我們這里需要的是以bit位為單位進行存放,每一位的狀態(tài)只有0和1兩種,這里用來表示該整數(shù)是否在位圖內(nèi)。
我們以一個×××為例,在一個×××的空間,存儲【1 6 9 4 12 10】這些數(shù),存儲結(jié)果應(yīng)該如下:
這個只給出了兩個字節(jié),全可以表示上面的6個整數(shù)。
關(guān)于位圖的底層,這里我們使用vector來模擬實現(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對應(yīng)位所在的下標(biāo) int num = x % 32; // num是x對應(yīng)該×××的第多少位 _vec[index] |= 1 << num; } void BitReSet(const size_t& x) { int index = x >> 5; // index是x對應(yīng)位所在的下標(biāo) int num = x % 32; // num是x對應(yīng)該×××的第多少位 _vec[index] &= (~(1 << num)); } bool BitTest(const size_t& x) { int index = x >> 5; // index是x對應(yīng)位所在的下標(biāo) int num = x % 32; // num是x對應(yīng)該×××的第多少位 return _vec[index] & (1 << num); } protected: vector<int> _vec; };
位圖的實現(xiàn)實際上就是進行一系列的位操作,通過位操作找到該×××對應(yīng)的位,下面給出一組簡單的測試用例
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; }
源碼庫中的位圖:
在源碼庫中,有這樣一個容器 bitset,和我們這里的bitmap性質(zhì)基本是一樣的,當(dāng)然,功能要比上面實現(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:
庫中提供了一系列的函數(shù)操作,除了set、reset、test之外,常用的還有filp<取反操作>,count<統(tǒng)計位為1的個數(shù)>。關(guān)于bitset的操作,都包含在
#include <bitset>
的頭文件中。
位圖的分析與擴展:
位圖的確用起來會很方便,但并不是任何情況下都需要使用到位圖的,位圖通常是為了處理大量數(shù)據(jù),內(nèi)存中不足以存放所有的數(shù)字才使用的一種數(shù)據(jù)結(jié)構(gòu),因為位圖也有著一定的缺陷:
1> 它的可讀性差
2> 位圖在視圖節(jié)約空間的時候,也伴隨著一定的消耗,它要求給最大值和最小值之間的所有數(shù)都要占用一個bit位,當(dāng)數(shù)據(jù)過于分散而數(shù)據(jù)量又不至太大的情況,位圖其實是一種比較浪費空間的做法。如果最小值為10000,位圖開辟出來的前10000個bit位其實就空了出來,沒有利用到,之前我們舉得例子,40億個整數(shù),因為無符號整數(shù)的最大值就到42.9億左右,大部分的整數(shù)值確定都已經(jīng)被取到,因此我們采用了位圖來實現(xiàn)。
3> 當(dāng)位圖用來存儲有符號整數(shù)時,有兩種解決方案,一種是我們約定好最小值不再從0開始,所有的計算都需要減去有符號整數(shù)的最大值,另一種是這里采用兩位來存儲一個數(shù),用兩位來表示正數(shù)、負(fù)數(shù)、不存在三種狀態(tài)。
試想,如果我們要求統(tǒng)計40億個無符號整數(shù)中,出現(xiàn)兩次以上的數(shù)該如何處理?
。。。。。。
同樣,多加一位標(biāo)志位,用兩個bit位來進行處理,那這樣的話,就需要我們自己來實現(xiàn)一個基本的兩位為一個單元的位圖結(jié)構(gòu)。
除此之外,位圖還可用來排序,判重,當(dāng)然這里僅僅限于無符號整數(shù),和上一節(jié)的哈希一樣,受限于整數(shù)范圍確實是個不好的地方,下一談會提到字符串哈希算法與布隆過濾器,正是由于字符串哈希算法,才使得這些數(shù)據(jù)結(jié)構(gòu)得以大范圍的使用。
關(guān)于哈希算法: http://muhuizz.blog.51cto.com/11321490/1870717
-----muhuizz整理
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。