數(shù)據(jù)結(jié)構(gòu)之位圖(bitmap)詳解
1. 概述
位圖(bitmap)是一種非常常用的結(jié)構(gòu),在索引,數(shù)據(jù)壓縮等方面有廣泛應(yīng)用。本文介紹了位圖的實(shí)現(xiàn)方法及其應(yīng)用場(chǎng)景。
2. 位圖實(shí)現(xiàn)
(1)自己實(shí)現(xiàn)
在位圖中,每個(gè)元素為“0”或“1”,表示其對(duì)應(yīng)的元素不存在或者存在。
#define INT_BITS sizeof(int)
#define SHIFT 5 // 2^5=32
#define MASK 0x1f // 2^5=32
#define MAX 1024*1024*1024 //max number
int bitmap[MAX / INT_BITS];
/*
* 設(shè)置第i位
* i >> SHIFT 相當(dāng)于 i / (2 ^ SHIFT),
* i&MASK相當(dāng)于mod操作 m mod n 運(yùn)算
*/
void set(int i) {
bitmap[i >> SHIFT] |= 1 << (i & MASK);
}
//獲取第i位
int test(int i) {
return bitmap[i >> SHIFT] & (1 << (i & MASK));
}
//清除第i位
int clear(int i) {
return bitmap[i >> SHIFT] & ~(1 << (i & MASK));
}
(2)函數(shù)庫(kù)實(shí)現(xiàn)
C++的STL中有bitmap類,它提供了很多方法,詳見(jiàn):http://www.cplusplus.com/reference/stl/bitset/
3. 位圖應(yīng)用
3.1 枚舉
(1)全組合
字符串全組合枚舉(對(duì)于長(zhǎng)度為n的字符串,組合方式有2^n種),如:abcdef,可以構(gòu)造一個(gè)從字符串到二進(jìn)制的映射關(guān)系,通過(guò)枚舉二進(jìn)制來(lái)進(jìn)行全排序。
null——> 000000
f——> 000001
e——> 000010
ef——> 000011
……
abcedf——> 111111
(2)哈米爾頓距離
枚舉算法,復(fù)雜度是O(N^2),怎樣降低復(fù)雜度呢?
如果是N 個(gè)二維的點(diǎn),那么我們可以怎么用較快的方法求出
通過(guò)簡(jiǎn)單的數(shù)學(xué)變形,我們可以得到這樣的數(shù)學(xué)公式:
通過(guò)觀察,我們發(fā)現(xiàn)每一對(duì)相同元的符號(hào)必定相反,如:x_i-y_i,于是我們有了一個(gè)二進(jìn)制思想的思路,那就是枚舉這些二i維的點(diǎn)的x 軸y 軸前的正負(fù)號(hào),這樣就可以用一個(gè)0~3 的數(shù)的二進(jìn)制形式來(lái)表示每個(gè)元素前面的正負(fù)號(hào),1表示+號(hào),0表示−號(hào),如:2 表示的二進(jìn)制位形式為10表示x_i-y_i。這樣我們就可以通過(guò)2^2*N次記錄下這些二元組的不同的符號(hào)的數(shù)值,對(duì)于每個(gè)二進(jìn)制來(lái)表示的不同的式子只需記錄下他們的值,這樣我們只需求max_i 和min_i出這些相同的二進(jìn)制表示的式子max_i –min_i,最后我們就可以解出ans=max{max_i-min_i}。
通過(guò)位圖,算法時(shí)間復(fù)雜度可將為O(N)。
3.2 搜索
設(shè)計(jì)搜索剪枝時(shí),需要保存已經(jīng)搜索過(guò)的歷史信息,有些情況下,可以使用位圖減小歷史信息數(shù)據(jù)所占空間。
3.3 壓縮
(1)在2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù),注,內(nèi)存不足以容納這2.5億個(gè)整數(shù)?
(2)騰訊面試題:給40億個(gè)不重復(fù)的unsigned int的整數(shù),沒(méi)排過(guò)序的,然后再給一個(gè)數(shù),如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中?
4. 總結(jié)
Bitmap是一種非常簡(jiǎn)潔快速的數(shù)據(jù)結(jié)構(gòu),他能同使證存儲(chǔ)空間和速度最優(yōu)化(而不必空間換時(shí)間)。
5. 參考資料
(1)《C實(shí)現(xiàn)bitmap位圖》:http://www.dbjr.com.cn/article/54438.htm
(2)武森《淺談信息學(xué)競(jìng)賽中的“0”和“1”》
相關(guān)文章
C語(yǔ)言實(shí)現(xiàn)電話簿管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)電話簿管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-12-12C語(yǔ)言指針基礎(chǔ)知識(shí)實(shí)例講解
這篇文章主要介紹了C語(yǔ)言指針基本知識(shí)實(shí)例講解,文中實(shí)例講解的很清晰,有不太懂的同學(xué)可以研究下2021-02-02C++中動(dòng)態(tài)綁定和內(nèi)存管理的實(shí)現(xiàn)
本文主要介紹了C++中動(dòng)態(tài)綁定和內(nèi)存管理的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2024-12-12C++中實(shí)現(xiàn)fibonacci數(shù)列的幾種方法
本文主要介紹了C++中實(shí)現(xiàn)fibonacci數(shù)列的幾種方法,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-01-01