RoaringBitmap原理及在Go中如何使用

這篇文章主要介紹了RoaringBitmap原理及在Go中如何使用的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇RoaringBitmap原理及在Go中如何使用文章都會有所收獲，下面我們一起來看看吧。

引言

我們看一道老生常談的面試題：

給定含有40億個不重復的位于[0, 2^32 - 1]區間內的整數的集合，如何快速判定某個數是否在該集合內？

首先，40 億在存儲上我們需要消耗 40億 * 32 位 = 160 Byte，大致是 16000 MB 即 14.9 GB 的內存，顯然這是我們不能接受的。如果你給出的是這個答案，那么你就已經輸了！

我們可以用位圖來存儲，第 0 個 bit 表示數字 0，第 1 個 Bit 表示數字 1，以此類推。如果某個數位于原集合內，就將它對應的位圖內的 bit 置為 1，否則保持為 0。這樣只占用了 512MB 的內存，不到原來的 3.4%。

我們會發現當數據稀疏的時候，也需要要開辟這么大的內存空間，就發揮不出其存儲效率。為了解決位圖不適應稀疏存儲的問題，RoaringBitmap（咆哮位圖）誕生了，因此本文重點探討它。下面簡稱 RBM。

1 什么是 RoaringBitmap

是一種基于位圖的數據結構，可以高效地存儲大量的非負整數，并支持多種集合運算，如并集、交集、差集等。它可以高效地判斷一個元素是否在集合中，并且可以使用很少的空間來存儲集合。

2 數據結構

源碼：

short[] keys;
Container[] values;
int size;

RoaringBitmap 當前有兩個版本，分別用來存儲 32 位和 64 位整數。以 32 位為例，RBM 會將 32 位的整形（int）拆分成高 16 位和低 16位 兩部分來處理。其中

• 高 16位 會被作為 key 存儲到 short[] keys中

• 低 16 位則被看做 value，存儲到 Container[] values中的某個 Container 中

keys 和 values 通過下標一一對應。size 則標示了當前包含的 key-value pair的數量，即 keys 和 values 中有效數據的數量。

注意：keys 數組永遠保持有序，方便二分查找！

3 三種 Container

Container 是 RoaringBitmap的核心，我們結合上面的圖會發現每個 32 位整形（int）的高 16 位已經作為key 存儲在 RoaringArray 中了，那么 Container 只需要處理低 16 位的數據即可。

3.1 ArrayContainer

源碼：

private static final int DEFAULT_INIT_SIZE = 4;
private static final int ARRAY_LAZY_LOWERBOUND = 1024;
static final int DEFAULT_MAX_SIZE = 4096;
private static final long serialVersionUID = 1L;
protected int cardinality;
short[] content;

從源碼可以可以看出 16 位數據 value 直接存儲在 short[] content中，因為是數組，始終保持順序存儲且不會重復，有利于二分查找。Container 存儲數據沒有任何壓縮，只適合存儲少量數據。

ArrayContainer 占用的空間大小與存儲的數據量為線性關系，每個 short 大小為 2 kb，所以存儲了 N 個數據的ArrayContainer 占用空間大致為 2N kb。存儲一個數據需要占用 2kb，存儲 4096 需要占用 8kb。

上面 DEFAULT_MAX_SIZE 值為 4096，可以知道，當容量超過這個值的時候會將當前 Container 替換為BitmapContainer。

3.2 BitmapContainer

源碼：

private static final int DEFAULT_INIT_SIZE = 4;
private static final int ARRAY_LAZY_LOWERBOUND = 1024;
static final int DEFAULT_MAX_SIZE = 4096;
private static final long serialVersionUID = 1L;
protected int cardinality;
short[] content;

BitmapContainer 底層用了 long[] 存儲位圖數據。RMB 每個 Container處理 16 位整形（int）數據，0~65535，需要 65536 個 bit 來存儲數據，每個 bit 位用 1 來表示有，0 來表示無。每個 long 有 64 位，所以需要 1024 個 long 來提供 65536 個 bit。

BitmapContainer 中無論存儲了 1 個還是存儲了 65536 個數據，其占用的空間都是同樣的 8 kb （4096）。

3.3 RunContainer

源碼：

private short[] valueslength;
int nbrruns;

RunContainer 又稱行程長度壓縮算法(Run Length Encoding)，在連續數據上壓縮效果顯著。

RunContainer 原理在連續出現的數字，只會記錄其初始數字和后續數量，舉個例子：

• 數列 22，它會壓縮為 22,0；

• 數列 22,23,24 它會壓縮為 22,3；

• 數列 22,23,24,32,33，它會壓縮為 22,3,32,1；

其中，short[] valueslength中存儲的就是壓縮后的數據。

可以看出，這種壓縮算法在性能和數據的連續性（緊湊性）關系極為密切，

• 在連續的 100 個 short，可以將 200 字節壓縮成 4 個 kb。

• 對于不連續的 100 個 short，編碼完之后會從 200 字節變為 400 kb。

如果要分析RunContainer的容量，我們可以做下面兩種極端的假設：

• 最優情況，只存在一個數據或者一串連續數字，存儲 2 個 short 會占用 4 kb。

• 最差情況，0~65535 的范圍內填充所有的不連續數字，(全部奇數位或全部偶數位)，需要存儲 65536 個short 占用 128 kb。

小結一下：

4 Go 使用 RoaringBitmap

Go 語言支持了 RoaringBitmap，安裝 roaring 庫：

go get -u github.com/RoaringBitmap/roaring
// go get -u github.com/RoaringBitmap/roaring/roaring64

RoaringBitmap 支持多種集合運算，包括并集、交集、差集、異或等，這些運算都可以在高效地處理大規模數據集的同時，避免內存溢出和性能問題。

下面介紹一些 RoaringBitmap 集合運算的示例：

4.1 并集運算

// 創建兩個 RoaringBitmap
rb1 := roaring.NewBitmap()
rb2 := roaring.NewBitmap()
// 添加元素
rb1.Add(1)
rb1.Add(2)
rb1.Add(3)
rb2.Add(3)
rb2.Add(4)
rb2.Add(5)
// 計算并集
rb3 := roaring.Or(rb1, rb2)
// 輸出結果
fmt.Println(rb3.ToArray())
// Output: [1 2 3 4 5]

4.2 交集運算

// 創建兩個 RoaringBitmap
rb1 := roaring.NewBitmap()
rb2 := roaring.NewBitmap()
// 添加元素
rb1.Add(1)
rb1.Add(2)
rb1.Add(3)
rb2.Add(3)
rb2.Add(4)
rb2.Add(5)
// 計算交集
rb3 := roaring.And(rb1, rb2)
// 輸出結果
fmt.Println(rb3.ToArray())
// Output: [3]

4.3 差集運算

// 創建兩個 RoaringBitmap
rb1 := roaring.NewBitmap()
rb2 := roaring.NewBitmap()
// 添加元素
rb1.Add(1)
rb1.Add(2)
rb1.Add(3)
rb2.Add(3)
rb2.Add(4)
rb2.Add(5)
// 計算差集
rb3 := roaring.AndNot(rb1, rb2)
// 輸出結果
fmt.Println(rb3.ToArray())
// Output: [1 2]

4.4 異或運算

// 創建兩個 RoaringBitmap
rb1 := roaring.NewBitmap()
rb2 := roaring.NewBitmap()
// 添加元素
rb1.Add(1)
rb1.Add(2)
rb1.Add(3)
rb2.Add(3)
rb2.Add(4)
rb2.Add(5)
// 計算異或
rb3 := roaring.Xor(rb1, rb2)
// 輸出結果
fmt.Println(rb3.ToArray())
// Output: [1 2 4 5]

小結一下，RoaringBitmap 可以很方便地進行集合運算，這些運算都可以在高效地處理大規模數據集的同時，避免內存溢出和性能問題。同時，RoaringBitmap 還提供了豐富的 API 接口，支持更多高級的操作和應用場景。

關于“RoaringBitmap原理及在Go中如何使用”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“RoaringBitmap原理及在Go中如何使用”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。