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