建站
咨詢
售后
建站咨詢
新聞中心
要點(diǎn)
- 位圖基本算法及其應(yīng)用場(chǎng)景。
- 位圖算法的優(yōu)化實(shí)現(xiàn)。
概述
位圖算法，是指使用一個(gè)bit位來(lái)表示數(shù)據(jù)狀態(tài)。通常應(yīng)用于海量數(shù)據(jù)去重、海量數(shù)據(jù)計(jì)算及判斷海量數(shù)據(jù)中是否存在某個(gè)數(shù)據(jù)的場(chǎng)景中。
以海量數(shù)據(jù)中是否存在某個(gè)數(shù)據(jù)的應(yīng)用場(chǎng)景為例，假設(shè)用16個(gè)bit位，分別表示數(shù)字0-15。bit位的值，表示該數(shù)字是否存在，0表示不存在，1表示存在。如上圖所示，在該數(shù)據(jù)集合中，存在的元素有1、2、6、10、11和13。
可以發(fā)現(xiàn)，在數(shù)據(jù)比較稠密的情況下，位圖算法能夠節(jié)約存儲(chǔ)空間，如圖中，使用2個(gè)字節(jié)便可以表示16個(gè)數(shù)字，同時(shí)可以在O(1)的時(shí)間復(fù)雜度下，判斷是否存在某個(gè)數(shù)字，大大提高了計(jì)算速度。
但是，在數(shù)據(jù)稀疏時(shí)，存儲(chǔ)空間會(huì)存在一定程度的浪費(fèi)。由于位圖算法中，位圖空間的大小是一定的，并不會(huì)根據(jù)存儲(chǔ)數(shù)據(jù)量的大小而改變。因此，當(dāng)位圖空間中存儲(chǔ)的數(shù)據(jù)量很小時(shí)，大量地位圖空間是空閑的，存在大量的浪費(fèi)。
算法實(shí)現(xiàn)
位圖算法在主流開(kāi)發(fā)語(yǔ)言中，都有對(duì)應(yīng)的實(shí)現(xiàn)?；静僮髦饕袑懭?、查詢、刪除、交集、并集等。下面通過(guò)一個(gè)示例來(lái)了解一下，位圖算法的實(shí)現(xiàn)。
位圖結(jié)構(gòu)定義例子使用char類型數(shù)組來(lái)存儲(chǔ)位圖信息(通常的實(shí)現(xiàn)中，會(huì)使用長(zhǎng)整型數(shù)組)，一個(gè)char類型有8個(gè)bit位。定義結(jié)構(gòu)如下：
// 為了簡(jiǎn)化問(wèn)題，LEN必須定義為CHAR_SIZE的倍數(shù)
#define LEN 16
#define CHAR_SIZE 8
typedef char BitSet[LEN/CHAR_SIZE];
寫入在某個(gè)bit位寫入數(shù)據(jù)時(shí)，首先通過(guò)整除，計(jì)算出該bit位在數(shù)組的哪個(gè)下標(biāo)，然后，用取余計(jì)算出char元素中的哪個(gè)bit上。最后通過(guò)或運(yùn)算將對(duì)應(yīng)位設(shè)置為1。
// 置bit位
void set(BitSet& bits, int pos) {
// 查找對(duì)應(yīng)數(shù)組下標(biāo)
int unit = pos / CHAR_SIZE;
// 查找在字節(jié)中的bit位
int p = pos % CHAR_SIZE;
// 通過(guò)與運(yùn)算實(shí)現(xiàn)對(duì)應(yīng)bit位置1
bits[unit] = bits[unit] | (0x1 << p);
查詢同寫入操作，先計(jì)算出bit位置，查找到對(duì)應(yīng)的bit位，然后返回該位置的數(shù)值。
// 查詢bit位
int get(BitSet& bits, int pos) {
// 查找對(duì)應(yīng)數(shù)組下標(biāo)
int unit = pos / CHAR_SIZE;
// 查找在字節(jié)中的bit位
int p = pos % CHAR_SIZE;
// 通過(guò)與運(yùn)算實(shí)現(xiàn)對(duì)應(yīng)bit位置1
return (bits[unit] & (0x1 << p)) > 0 ? 1 : 0;
}
刪除首先查找到對(duì)應(yīng)的位置，然后通過(guò)與運(yùn)算將該位置清空。
// 清空bit位
void clear(BitSet& bits, int pos) {
// 查找對(duì)應(yīng)數(shù)組下標(biāo)
int unit = pos / CHAR_SIZE;
// 查找在字節(jié)中的bit位
int p = pos % CHAR_SIZE;
// 通過(guò)與運(yùn)算實(shí)現(xiàn)對(duì)應(yīng)bit位置1
bits[unit] = bits[unit] & (~(0x1 << p));
}
交集對(duì)數(shù)組逐個(gè)元素進(jìn)行或運(yùn)算。
// 求位圖b1和b2的并集
void unionn(const BitSet& b1, const BitSet& b2, BitSet& res) {
for (auto i = 0; i < (LEN/CHAR_SIZE); ++i) {
res[i] = b1[i] | b2[i];
}
}
并集對(duì)數(shù)組逐元素進(jìn)行與運(yùn)算。
// 求位圖b1和b2的交集
void inter(const BitSet& b1, const BitSet& b2, BitSet& res) {
for (auto i = 0; i < (LEN/CHAR_SIZE); ++i) {
res[i] = b1[i] & b2[i];
}
}
在生產(chǎn)實(shí)現(xiàn)時(shí)，可能會(huì)進(jìn)行一些優(yōu)化：
- 使用CPU指令優(yōu)化，如SSE等，一次能進(jìn)行128位的運(yùn)算，可以提高計(jì)算速度。
- 某些業(yè)務(wù)場(chǎng)景下，一個(gè)數(shù)據(jù)狀態(tài)可能有大于2個(gè)，可以使用多個(gè)bit位來(lái)表示一個(gè)數(shù)據(jù)狀態(tài)。
擴(kuò)展
為了解決位圖稀疏時(shí)，位圖低效率的問(wèn)題，工業(yè)界，有多種位圖壓縮算法，其中，最經(jīng)典的是RoaringBitmap。
RoaringBitmap的核心思想是，將整數(shù)進(jìn)行分桶，高16位的值作為其桶的索引，每個(gè)桶對(duì)應(yīng)一個(gè)容器。如下圖所示：
roaring bitmap
容器的結(jié)構(gòu)有三種類型：有序數(shù)組、未壓縮位圖、和行程長(zhǎng)度編碼。
- 有序數(shù)組：當(dāng)?shù)?6位中，元素個(gè)數(shù)小于4096時(shí)，采用有序數(shù)組的結(jié)構(gòu)進(jìn)行存儲(chǔ)。在查找元素時(shí)，使用二分查找方法。取值4096的原因是，存儲(chǔ)4096個(gè)16位的整數(shù)，所占用的存儲(chǔ)空間：。
- 未壓縮位圖：未壓縮位圖的存儲(chǔ)結(jié)果就是本文所描述的位圖存儲(chǔ)結(jié)構(gòu)，使用一個(gè)固定的連續(xù)內(nèi)存塊實(shí)現(xiàn)。
- 行程長(zhǎng)度編碼(run-length encoding)：行程長(zhǎng)度編碼是一種無(wú)損數(shù)據(jù)壓縮技術(shù)，其原理是，將連續(xù)出現(xiàn)的數(shù)據(jù)存儲(chǔ)為起始值和計(jì)算兩部分。比如，數(shù)據(jù)列表[1,2,3,4,5,6]存儲(chǔ)為[1,5]，表示以1開(kāi)始，后面連續(xù)遞增5個(gè)數(shù)值。在很多實(shí)現(xiàn)中，行程長(zhǎng)度編碼容器，需要手動(dòng)調(diào)用，才能轉(zhuǎn)換為該容器。
在進(jìn)行插入和刪除操作之后，需要根據(jù)元素個(gè)數(shù)進(jìn)行容器轉(zhuǎn)換。插入元素時(shí)，若元素個(gè)數(shù)達(dá)到4096，則需要轉(zhuǎn)換為未壓縮位圖進(jìn)行存儲(chǔ)。刪除元素時(shí)，若元素個(gè)數(shù)小于4096時(shí)，則需要轉(zhuǎn)換為有序數(shù)組存儲(chǔ)。
參考
- Better bitmap performance with Roaring bitmaps。
- Consistently faster and smaller compressed bitmaps with Roaring。
- https://github.com/RoaringBitmap/CRoaring.git。
本文名稱：一篇帶給你索引技術(shù)之位圖
文章出自：http://www.dlmjj.cn/article/cdsdocd.html
