咆哮位圖簡介

一、概述

在本教程中，我們將了解咆哮位圖。我們將使用一些對集合的基本操作作為對咆哮位圖的示例。此外，我們將在 Java 中執行RoaringBitmap和BitSet之間的性能測試。

二、咆哮位圖介紹

由於其高性能和壓縮比，咆哮的位圖數據結構通常用於分析、搜索和大數據項目。它背後的想法來自位圖索引，一種有效表示數字數組的數據結構。它類似於 Java BitSet ，但經過壓縮。

壓縮大整數集同時保持對單個元素的快速訪問是咆哮位圖的重要優勢。 Roaring bitmap 在內部使用不同類型的容器來實現這一點。

3. 咆哮位圖的工作原理

咆哮位圖是一組無符號整數，由不相交子集的容器組成。每個子集都有一個 16 位密鑰索引，可以保存 2^16 範圍內的值。這允許將無符號的 32 位整數存儲為 Java short s，因為最壞的情況只需要 16 位來表示單個 32 位值。容器大小的選擇還確保在最壞的情況下，容器仍然適合現代 CPU 的L1緩存。

下圖表示咆哮位圖結構的外觀：

RoaringBitMap

我們的整數的 16 個最高有效位是桶或塊鍵。每個數據塊代表區間中值範圍的基數 (0<= n < 2^16)。此外，如果值範圍內沒有數據，則不會創建塊。

下圖是具有不同數據的咆哮位圖示例：

帶有數據的

在第一個塊中，我們存儲了 2 的前 10 個倍數。此外，在第二個塊中，我們有 100 個從 65536 開始的連續整數。圖像中的最後一個塊具有 131072 到 19660 之間的偶數。

4. 咆哮位圖中的容器

咆哮位圖中的容器主要分為三種——數組、位圖和運行容器。根據分區集的特性，Run Container、Bitmap Container 或 Array Container 是保存分區數據的容器的實現。

當我們向 roaring bitmap 添加數據時，在內部，它會根據值是否適合容器鍵覆蓋的範圍來決定是創建一個新容器還是更改現有容器。

4.1.咆哮位圖的數組容器

Array Container 不壓縮數據，只容納少量數據。它佔用的空間量與其保存的數據量成正比：每個都是兩個字節。

Array Container 使用的數據類型是short數據類型。整數按排序順序存儲。

另外，數組初始容量為4，最大元素數為4096 ，數組容量是動態變化的。但是咆哮位圖在元素個數超過4096時，會在內部將Array Container轉為Bitmap Container。

讓我們看一個將數據插入到咆哮位圖中的數組容器的示例。我們有數字 131090。16 個最高有效位是 0000 0000 0000 0010，這是我們的密鑰。低16位是0000 0000 0001 0010。當我們將它轉換為十進制時，它的值為18。現在，我們插入數據後，這是我們咆哮的位圖結構：

RoaringBitmap

我們可以注意到，插入後，Array Container 的基數對於最高 16 位代表的鍵為 5。

4.2. Roaring Bitmap 的位圖容器

Bitmap Container 是 bitset 的經典實現。

咆哮位圖使用了一個long數組來存儲位圖數據。數組容量恆定為 1024，不像 Array Container 是一個動態擴展的數組。位圖容器不需要找到位置。相反，它直接訪問索引。

為了觀察它是如何工作的，我們將使用一個簡單的例子。我們將把數字 32786 插入到咆哮位圖中。前 16 位是 0000 0000 0000 0000。其餘位是 1000 0000 0001 0010 或十進製表示的 32786。該值表示要在位圖容器中設置的索引。讓我們看看帶有新信息的咆哮位圖：

RoaringBitmap

4.3. `RoaringBitmap`的運行容器

當位圖的一個區域有大量乾淨的字時，運行長度編碼 (RLE) 是最佳的容器選擇。它使用short數據類型數組。

偶數索引處的值表示運行的開始，奇數索引處的值表示這些運行的長度。容器的基數是通過遍歷完整的運行數組來計算的。

例如，下圖向我們展示了一個包含連續整數序列的容器。然後，在 RLE 執行之後，容器只有四個值：

RLE容器

這些值表示為 11 後跟四個連續增加的值和 27 後跟兩個連續增加的值。

這種壓縮算法的工作原理取決於數據的緊湊程度或連續程度。如果我們有 100 個short都是連續的，它可以將它們從 200 字節壓縮到 4 字節，但是如果它們都在不同的地方，編碼後它會從 200 字節變成 400 字節。

5. `RoaringBitmap`中的 Union

在簡要介紹了 roaring bitmap 之後，在我們進入代碼示例之前，我們需要將RoaringBitmap依賴項添加到我們的pom.xml文件中：

<dependency>
 <groupId>org.roaringbitmap</groupId>
 <artifactId>RoaringBitmap</artifactId>
 <version>0.9.38</version>
 </dependency>

集合的並集是測試咆哮位圖的第一個操作。首先，讓我們聲明兩個RoaringBitmap實例。第一個是A ，第二個是B ：

@Test
 void givenTwoRoaringBitmap_whenUsingOr_thenWillGetSetsUnion() {
 RoaringBitmap expected = RoaringBitmap.bitmapOf(1, 2, 3, 4, 5, 6, 7, 8);
 RoaringBitmap A = RoaringBitmap.bitmapOf(1, 2, 3, 4, 5);
 RoaringBitmap B = RoaringBitmap.bitmapOf(4, 5, 6, 7, 8);
 RoaringBitmap union = RoaringBitmap.or(A, B);
 assertEquals(expected, union);
 }

在上面的代碼中，我們聲明了兩個RoaringBitmap實例。我們使用RoaringBitmap提供的bitmapOf()靜態工廠方法來創建實例。然後，我們使用or()方法執行集合併集操作。在幕後，這個操作完成了設置位圖之間的邏輯OR 。這是一個線程安全的操作。

6. `RoaringBitmap`中的交點

我們可以對我們的集合執行的另一個有用的操作是交集。

讓我們針對交集問題實施我們的測試用例。與聯合一樣，交集操作在RoaringBitmap中非常簡單：

@Test
 void givenTwoRoaringBitmap_whenUsingAnd_thenWillGetSetsIntersection() {
 RoaringBitmap expected = RoaringBitmap.bitmapOf(4, 5);
 RoaringBitmap A = RoaringBitmap.bitmapOfRange(1, 6);
 RoaringBitmap B = RoaringBitmap.bitmapOf(4, 5, 6, 7, 8);
 RoaringBitmap intersection = RoaringBitmap.and(A, B);
 assertEquals(expected, intersection);
 }

我們使用來自RoaringBitmap類的另一個靜態工廠方法在此測試用例中聲明A集。 bitmapOfRange()靜態方法創建一個新的RoaringBitmap.在引擎蓋下， bitmapOfRange()方法創建一個新實例並使用add()方法將範圍內的數據添加到 roaring bitmap 。在這種情況下， add()方法接收兩個long值作為表示下限和上限的參數。下限是包容性的。相比之下，上限被排除在結果集範圍之外。 add()方法接收兩個int值作為參數，在當前 API 版本中已棄用。

然後，我們使用and()方法來執行我們的交集操作。顧名思義， and()方法在兩個集合之間執行邏輯AND操作。此操作是線程安全的。

7. `RoaringBitmap`的區別

除了並集和交集，我們還有集合運算的相對補集。

接下來，讓我們用RoaringBitmap構建我們的設置差異測試用例：

@Test
 void givenTwoRoaringBitmap_whenUsingAndNot_thenWillGetSetsDifference() {
 RoaringBitmap expected = RoaringBitmap.bitmapOf(1, 2, 3);
 RoaringBitmap A = new RoaringBitmap();
 A.add(1L, 6L);
 RoaringBitmap B = RoaringBitmap.bitmapOf(4, 5, 6, 7, 8);
 RoaringBitmap difference = RoaringBitmap.andNot(A, B);
 assertEquals(expected, difference);
 }

與我們之前的代碼示例一樣，我們聲明了兩個集合A和B對於這種情況，我們使用不同的方法來實例化A集。我們首先創建一個空的RoaringBitmap 。然後，我們使用add()方法，與上一節中描述的bitmapOfRange()方法使用的方法相同。

andNot()方法執行A和B之間的集合差異。從邏輯的角度來看，這個操作執行的是按位ANDNOT （差）運算。只要給定的位圖保持不變，此操作就是線程安全的。

8. `RoaringBitmap`中的異或操作

此外，我們在咆哮位圖中進行了 XOR（異或）操作。此操作類似於集合的相對補集，但結果集中省略了兩個集合之間的公共元素。

我們使用xor()方法來執行此操作。讓我們進入我們的測試代碼示例：

@Test
 void givenTwoRoaringBitmap_whenUsingXOR_thenWillGetSetsSymmetricDifference() {
 RoaringBitmap expected = RoaringBitmap.bitmapOf(1, 2, 3, 6, 7, 8);
 RoaringBitmap A = RoaringBitmap.bitmapOfRange(1, 6);
 RoaringBitmap B = RoaringBitmap.bitmapOfRange(4, 9);
 RoaringBitmap xor = RoaringBitmap.xor(A, B);
 assertEquals(expected, xor);
 }

簡而言之， RoaringBitmap類中的xor()方法執行的是按XOR異或運算，是線程安全的。

9. 比較`BitSet`性能

此外，讓我們在RoaringBitmap和 Java BitSet.對於每個集合類型，我們測試前面描述的操作：聯合、交集、差異和異或。

我們使用 Java Microbenchmark Harness (JMH) 來實施我們的性能測試。首先，我們需要將依賴項添加到我們的pom.xml文件中：

<dependency>
 <groupId>org.openjdk.jmh</groupId>
 <artifactId>jmh-generator-annprocess</artifactId>
 <version>1.36</version>
 </dependency>
 <dependency>
 <groupId>org.openjdk.jmh</groupId>
 <artifactId>jmh-core</artifactId>
 <version>1.36</version>
 </dependency>

最新版本的JMH Core和JMH Annotation Processor依賴項可以在 Maven Central 中找到。

9.1.聲明基準範圍

接下來，我們在為測試設置初始條件時聲明我們的類和集合：

@State(Scope.Thread)
 class BitSetsBenchmark {
 private RoaringBitmap rb1;
 private BitSet bs1;
 private RoaringBitmap rb2;
 private BitSet bs2;
 private final static int SIZE = 10_000_000;
 }

最初，我們為每種類型聲明了兩組， BitSet和RoaringBitmap 。然後，我們設置一個最大尺寸。 SIZE變量是我們將用作集合大小的上限。

我們將在本課程中執行所有測試。此外，我們使用Scope.Thread作為State和默認的Throughput基準模式。

我們將在操作後生成一個新集合，以避免改變我們的輸入數據結構。避免突變對於並發上下文很重要。這就是為什麼，對於BitSet案例，我們將克隆輸入集，這樣結果數據就不會改變輸入集。

9.2.基準數據設置

接下來，讓我們為測試設置數據：

@Setup
 public void setup() {
 rb1 = new RoaringBitmap();
 bs1 = new BitSet(SIZE);
 rb2 = new RoaringBitmap();
 bs2 = new BitSet(SIZE);
 for (int i = 0; i < SIZE / 2; i++) {
 rb1.add(i);
 bs1.set(i);
 }
 for (int i = SIZE / 2; i < SIZE; i++) {
 rb2.add(i);
 bs2.set(i);
 }
 }

我們的兩個BitSet集被初始化為SIZE 。然後，對於第一個RoaringBitmap和BitSet ，我們將值添加/設置為SIZE / 2,不包括在內。對於其他兩組，我們將SIZE / 2的值添加到SIZE 。

9.3.基準測試

最後，讓我們編寫測試代碼。讓我們從聯合操作開始：

@Benchmark
 public RoaringBitmap roaringBitmapUnion() {
 return RoaringBitmap.or(rb1, rb2);
 }
 @Benchmark
 public BitSet bitSetUnion() {
 BitSet result = (BitSet) bs1.clone();
 result.or(bs2);
 return result;
 }

第二個操作是交集：

@Benchmark
 public RoaringBitmap roaringBitmapIntersection() {
 return RoaringBitmap.and(rb1, rb2);
 }
 @Benchmark
 public BitSet bitSetIntersection() {
 BitSet result = (BitSet) bs1.clone();
 result.and(bs2);
 return result;
 }

第三個是區別：

@Benchmark
 public RoaringBitmap roaringBitmapDifference() {
 return RoaringBitmap.andNot(rb1, rb2);
 }
 @Benchmark
 public BitSet bitSetDifference() {
 BitSet result = (BitSet) bs1.clone();
 result.andNot(bs2);
 return result;
 }

最後一個是異或運算：

@Benchmark
 public RoaringBitmap roaringBitmapXOR() {
 return RoaringBitmap.xor(rb1, rb2);
 }
 @Benchmark
 public BitSet bitSetXOR() {
 BitSet result = (BitSet) bs1.clone();
 result.xor(bs2);
 return result;
 }

9.4.基準測試結果

執行我們的基準測試後，我們得到以下結果：

Benchmark Mode Cnt Score Error Units
 BitSetsBenchmark.bitSetDifference thrpt 25 3890.694 ± 313.808 ops/s
 BitSetsBenchmark.bitSetIntersection thrpt 25 3542.387 ± 296.007 ops/s
 BitSetsBenchmark.bitSetUnion thrpt 25 3012.666 ± 503.821 ops/s
 BitSetsBenchmark.bitSetXOR thrpt 25 2872.402 ± 348.099 ops/s
 BitSetsBenchmark.roaringBitmapDifference thrpt 25 12930.064 ± 527.289 ops/s
 BitSetsBenchmark.roaringBitmapIntersection thrpt 25 824167.502 ± 30176.431 ops/s
 BitSetsBenchmark.roaringBitmapUnion thrpt 25 6287.477 ± 250.657 ops/s
 BitSetsBenchmark.roaringBitmapXOR thrpt 25 6060.993 ± 607.562 ops/s

我們可以注意到， RoaringBitmap比BitSet操作執行得更好。儘管有這些結果，但我們需要考慮何時使用每種類型。

在某些情況下嘗試使用壓縮位圖是一種浪費。例如，這可能是我們有一個小數據世界的時候。如果我們可以在不增加內存使用的情況下解壓縮BitSet ，那麼壓縮位圖可能不適合我們。如果不需要壓縮， BitSet可提供出色的速度。

10.結論

在本文中，我們了解了咆哮的位圖數據結構。我們討論了RoaringBitmap的一些操作。此外，我們在RoaringBitmap和BitSet之間進行了一些性能測試。結果，我們了解到前者的表現優於後者。

和往常一樣，我們示例的源代碼可以在 GitHub 上找到。

本作品係原創或者翻譯，採用《署名-非商業性使用-禁止演繹4.0國際》許可協議