«

RoaringBitmap原理及在Go中如何使用

时间:2024-8-6 09:04     作者:韩俊     分类: 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 接口,支持更多高级的操作和应用场景。

标签: golang

热门推荐