Go 每日一库之 roaring

简介

集合是软件中的基本抽象。实现集合的方法有很多，例如 hash set、tree等。要实现一个整数集合，位图（bitmap，也称为 bitset 位集合，bitvector 位向量）是个不错的方法。使用 n 个位（bit），我们可以表示整数范围[0, n)。如果整数 i 在集合中，第 i 位设置为 1。这样集合的交集（intersection）、并集（unions）和差集（difference）可以利用整数的按位与、按位或和按位与非来实现。而计算机执行位运算是非常迅速的。

上一篇文章我介绍了bitset这个库。

bitset 在某些场景中会消耗大量的内存。例如，设置第 1,000,000 位，需要占用超过 100kb 的内存。为此 bitset 库的作者又开发了压缩位图库：roaring。

本文首先介绍了 roaring 的使用。最后分析 roaring 的文件存储格式。

安装

本文代码使用 Go Modules。

创建目录并初始化：

$ mkdir -p roaring && cd roaring
$ go mod init github.com/darjun/go-daily-lib/roaring

安装roaring库：

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

使用

基本操作

func main() {
  bm1 := roaring.BitmapOf(1, 2, 3, 4, 5, 100, 1000)
  fmt.Println(bm1.String())         // {1,2,3,4,5,100,1000}
  fmt.Println(bm1.GetCardinality()) // 7
  fmt.Println(bm1.Contains(3))      // true

  bm2 := roaring.BitmapOf(1, 100, 500)
  fmt.Println(bm2.String())         // {1,100,500}
  fmt.Println(bm2.GetCardinality()) // 3
  fmt.Println(bm2.Contains(300))    // false

  bm3 := roaring.New()
  bm3.Add(1)
  bm3.Add(11)
  bm3.Add(111)
  fmt.Println(bm3.String())         // {1,11,111}
  fmt.Println(bm3.GetCardinality()) // 3
  fmt.Println(bm3.Contains(11))     // true

  bm1.Or(bm2)                       // 执行并集
  fmt.Println(bm1.String())         // {1,2,3,4,5,100,500,1000}
  fmt.Println(bm1.GetCardinality()) // 8
  fmt.Println(bm1.Contains(500))    // true

  bm2.And(bm3)                      // 执行交集
  fmt.Println(bm2.String())         // {1}
  fmt.Println(bm2.GetCardinality()) // 1
  fmt.Println(bm2.Contains(1))      // true
}

上面演示了两种创建 roaring bitmap 的方式：

• roaring.BitmapOf()：传入集合元素，创建位图并添加这些元素

• roaring.New()：创建一个空位图