欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Go壓縮位圖庫roaring安裝使用詳解

 更新時間:2022年07月22日 09:28:12   作者:darjun  
這篇文章主要為大家介紹了Go壓縮位圖庫roaring安裝使用詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪

簡介

集合是軟件中的基本抽象。實現(xiàn)集合的方法有很多,例如 hash set、tree等。要實現(xiàn)一個整數(shù)集合,位圖(bitmap,也稱為 bitset 位集合,bitvector 位向量)是個不錯的方法。使用 n 個位(bit),我們可以表示整數(shù)范圍[0, n)。如果整數(shù) i 在集合中,第 i 位設置為 1。這樣集合的交集(intersection)、并集(unions)和差集(difference)可以利用整數(shù)的按位與、按位或和按位與非來實現(xiàn)。而計算機執(zhí)行位運算是非常迅速的。

上一篇文章我介紹了bitset這個庫。

bitset 在某些場景中會消耗大量的內存。例如,設置第 1,000,000 位,需要占用超過 100kb 的內存。為此 bitset 庫的作者又開發(fā)了壓縮位圖庫:roaring。

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

安裝

本文代碼使用 Go Modules。

創(chuàng)建目錄并初始化:

$ 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)                       // 執(zhí)行并集
  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)                      // 執(zhí)行交集
  fmt.Println(bm2.String())         // {1}
  fmt.Println(bm2.GetCardinality()) // 1
  fmt.Println(bm2.Contains(1))      // true
}

上面演示了兩種創(chuàng)建 roaring bitmap 的方式:

  • roaring.BitmapOf():傳入集合元素,創(chuàng)建位圖并添加這些元素
  • roaring.New():創(chuàng)建一個空位圖

首先,我們創(chuàng)建了一個位圖 bm1:{1,2,3,4,5,100,1000}。輸出它的字符串表示,集合大小,檢查 3 是否在集合中。

然后又創(chuàng)建了一個位圖 bm2:{1,100,500}。輸出檢查三連。

接著創(chuàng)建了一個空位圖 bm3,依次添加元素 1,11,111。輸出檢查三連。

然后我們對 bm1 和 bm2 執(zhí)行并集,結果直接存放在 bm1 中。由于集合中的元素各不相同,此時 bm1 中的元素為{1,2,3,4,5,100,500,1000},大小為 8。

再然后我們對 bm2 和 bm3 執(zhí)行交集,結果直接存放在 bm2 中。此時 bm2 中的元素為{1},大小為 1。

可以看出 roaring 提供的基本操作與 bitset 大體相同。只是命名完全不一樣,在使用時需要特別注意。

  • bm.String():返回 bitmap 的字符串表示
  • bm.Add(n):添加元素 n
  • bm.GetCardinality():返回集合的基數(shù)(Cardinality),即元素個數(shù)
  • bm1.And(bm2):執(zhí)行集合交集,會修改 bm1
  • bm1.Or(bm2):執(zhí)行集合并集,會修改 bm1

迭代

roaring 位圖支持迭代。

func main() {
  bm := roaring.BitmapOf(1, 2, 3, 4, 5, 100, 1000)
  i := bm.Iterator()
  for i.HasNext() {
    fmt.Println(i.Next())
  }
}

與很多編程語言支持的迭代器一樣,先調用對象的Iterator()返回一個迭代器,然后循環(huán)調用HasNext()檢查是否有下一個元素,調用i.Next()返回下一個元素。

上面代碼依次輸出 1,2,3,4,5,100,1000。

并行操作

roaring 支持位圖集合運算的并行執(zhí)行??梢灾付ㄊ褂枚嗌賯€ goroutine 對集合執(zhí)行交集、并集等。同時可以傳入可變數(shù)量的位圖集合:

func main() {
  bm1 := roaring.BitmapOf(1, 2, 3, 4, 5, 100, 1000)
  bm2 := roaring.BitmapOf(1, 100, 500)
  bm3 := roaring.BitmapOf(1, 10, 1000)
  bmAnd := roaring.ParAnd(4, bm1, bm2, bm3)
  fmt.Println(bmAnd.String())         // {1}
  fmt.Println(bmAnd.GetCardinality()) // 1
  fmt.Println(bmAnd.Contains(1))      // true
  fmt.Println(bmAnd.Contains(100))    // false
  bmOr := roaring.ParOr(4, bm1, bm2, bm3)
  fmt.Println(bmOr.String())         // {1,2,3,4,5,10,100,500,1000}
  fmt.Println(bmOr.GetCardinality()) // 9
  fmt.Println(bmOr.Contains(10))     // true
}

并行操作使用相應接口的Par*版本,第一個參數(shù)指定 worker 數(shù)量,接著傳入任意多個 bitmap。

寫入與讀取

roaring 可以將壓縮的位圖寫入到文件中,并且格式與其他語言的實現(xiàn)保持兼容。也就是說,我們可以用 Go 將 roaring 位圖寫入文件,然后通過網絡發(fā)送給另一臺機器,在這臺機器上使用 C++ 或 Java 的實現(xiàn)讀取這個文件。

func main() {
  bm := roaring.BitmapOf(1, 3, 5, 7, 100, 300, 500, 700)
  buf := &bytes.Buffer{}
  bm.WriteTo(buf)
  newBm := roaring.New()
  newBm.ReadFrom(buf)
  if bm.Equals(newBm) {
    fmt.Println("write and read back ok.")
  }
}
  • WriteTo(w io.Writer):寫入一個 io.Writer,可以是內存(byte.Buffer),可以是文件(os.File),甚至可以是網絡(net.Conn)
  • ReadFrom(r io.Reader):從一個 io.Reader 中讀取,來源同樣可以是內存、文件或網絡等

注意WriteTo的返回值為sizeerr,使用時需要處理錯誤情況。ReadFrom也是返回sizeerr,同樣需要處理處理。

64 位版本

默認情況下,roaring 位圖只能用來存儲 32 位整數(shù)。所以 roaring 位圖最多能包含 4294967296(2^32) 個整數(shù)。

roaring 也提供了存儲 64 位整數(shù)的擴展,即github.com/RoaringBitmap/roaring/roaring64。提供的接口基本相同。然而,64 位版本不保證與 Java/C++ 等格式兼容。

存儲格式

roaring 可以寫入文件中,也可以從文件中讀取。并且提供多種語言兼容的格式。下面我們一起來看看存儲的格式。

roaring 位圖默認只能存儲 32 位的整數(shù)。在序列化時,將這些整數(shù)分容器(container)存儲。每個容器有一個 16 位表示的基數(shù)(Cardinality,即元素個數(shù),范圍[1,2^16])和一個鍵(key)。鍵取元素的最高有效 16 位(most significant),所以鍵的范圍為[0, 65536)。這樣如果兩個整數(shù)的最高 16 位有效位相同,那么它們將被保存在同一個容器中。這樣做還有一個好處:可以減少占用的空間。

所有整數(shù)均采用小端存儲。

概覽

roaring 采用的存儲格式布局如下:

從上到下依次介紹。

開始部分是一個 Cookie Header。它用來識別一個二進制流是不是一個 roaring 位圖,并且存儲一些少量信息。

cookie 這個詞有點意思,本意是餅干。我的理解是指小物件,所以 http 中的 cookie 只是用來存儲少量信息。這里的 Cookie Header 也是如此。

接下來是 Descriptive Header。見名知義,它用來描述容器的信息。后面會詳細介紹容器。

接下來有一個可選的 Offset Header。它記錄了每個容器相對于首位的偏移,這讓我們可以隨機訪問任意容器。

最后一部分是存儲實際數(shù)據的容器。roaring 中一共有 3 種類型的容器:

  • array(數(shù)組型):16bit 整數(shù)數(shù)組
  • bitset(位集型):使用上一篇文章介紹的 bitset 存儲數(shù)據
  • run:這個有點不好翻譯。有些人可能聽說過 run-length 編碼,有翻譯成游程編碼的。即使用長度+數(shù)據來編碼,比如"0000000000"可以編碼成"10,0",表示有 10 個 0。run 容器也是類似的,后文詳述

設計這種的布局,是為了不用將存儲的位圖全部載入內存就可以隨機讀取它的數(shù)據。并且每個容器的范圍相互獨立,這使得并行計算變得容易。

Cookie Header

Cookier Header 有兩種類型,分別占用 32bit 和 64bit 的空間。

第一種類型,前 32bit 的值為 12346,此時緊接著的 32bit 表示容器數(shù)量(記為 n)。同時這意味著,后面沒有 run 類型的容器。12346 這魔術數(shù)字被定義為常量SERIAL_COOKIE_NO_RUNCONTAINER,含義不言自明。

第二種類型,前 32bit 的最低有效 16 位的值為 12347。此時,最高有效 16 位存儲的值等于容器數(shù)量-1。將 cookie 右移 16 位再加 1 即可得到容器數(shù)量。由于這種類型的容器數(shù)量不會為 0,采用這種編碼我們能的容器數(shù)量會多上 1 個。這種方法在很多地方都有應用,例如 redis。后面緊接著會使用 (n+7)/8 字節(jié)(作為一個 bitset)表示后面的容器是否 run 容器。每位對應一個容器,1 表示對應的容器是 run 容器,0 表示不是 run 容器。

由于是小端存儲,所以流的前 16bit 一定是 12346 或 12347。如果讀取到了其它的值,說明文件損壞,直接退出程序即可。

Descriptive Header

Cookie Header 之后就是 Descriptive Header。它使用一對 16bit 數(shù)據描述每個容器。一個 16bit 存儲鍵(即整數(shù)的最高有效 16bit),另一個 16bit 存儲對應容器的基數(shù)(Cardinality)-1(又見到了),即容器存儲的整數(shù)數(shù)量)。如果有 n 個容器,則 Descriptive Header 需要 32n 位 或 4n 字節(jié)。

掃描 Descriptive Header 之后,我們就能知道每個容器的類型。如果 cookie 值為 12347,cookie 后有一個 bitset 表示每個容器是否是 run 類型。對于非 run 類型的容器,如果容器的基數(shù)(Cardinality)小于等于 4096,它是一個 array 容器。反之,這是一個 bitset 容器

Offset Header

滿足以下任一條件,Offset Header 就會存在:

  • cookie 的值為 SERIAL_COOKIE_NO_RUNCONTAINER(即 12346)
  • cookie 的值為 SERIAL_COOKIE(即 12347),并且至少有 4 個容器。也有一個常量NO_OFFSET_THRESHOLD = 4

Offset Header 為每個容器使用 32bit 值存儲對應容器距離流開始處的偏移,單位字節(jié)。

Container

接下來就是實際存儲數(shù)據的容器了。前面簡單提到過,容器有三種類型。

array

存儲有序的 16bit 無符號整數(shù)值,有序便于使用二分查找提高效率。16bit 值只是數(shù)據的最低有效 16bit,還記得 Descriptive Header 中每個容器都有一個 16bit 的 key 吧。將它們拼接起來才是實際的數(shù)據。

如果容器有 x 個值,占用空間 2x 字節(jié)。

bitmap/bitset

bitset 容器固定使用 8KB 的空間,以 64bit 為單位(稱為字,word)序列化。因此,如果值 j 存在,則第 j/64 個字(從 0 開始)的 j%64 位會被設置為 1(從 0 開始)。

run

以一個表示 run 數(shù)量的 16bit 整數(shù)開始。后續(xù)每個 run 用一對 16bit 整數(shù)表示,前一個 16bit 表示開始的值,后一個 16bit 表示長度-1(又雙見到了)。例如,11,4 表示數(shù)據 11,12,13,14,15。

手擼解析代碼

驗證我們是否真的理解了 roaring 布局最有效的方法就是手擼一個解析。使用標準庫encoding/binary可以很容易地處理大小端問題。

定義常量:

const (
  SERIAL_COOKIE_NO_RUNCONTAINER = 12346
  SERIAL_COOKIE                 = 12347
  NO_OFFSET_THRESHOLD           = 4
)

讀取 Cookie Header:

func readCookieHeader(r io.Reader) (cookie uint16, containerNum uint32, runFlagBitset []byte) {
  binary.Read(r, binary.LittleEndian, &cookie)
  switch cookie {
  case SERIAL_COOKIE_NO_RUNCONTAINER:
    var dummy uint16
    binary.Read(r, binary.LittleEndian, &dummy)
    binary.Read(r, binary.LittleEndian, &containerNum)
  case SERIAL_COOKIE:
    var u16 uint16
    binary.Read(r, binary.LittleEndian, &u16)
    containerNum = uint32(u16)
    buf := make([]uint8, (containerNum+7)/8)
    r.Read(buf)
    runFlagBitset = buf[:]
  default:
    log.Fatal("unknown cookie")
  }
  fmt.Println(cookie, containerNum, runFlagBitset)
  return
}

讀取 Descriptive Header:

func readDescriptiveHeader(r io.Reader, containerNum uint32) []KeyCard {
  var keycards []KeyCard
  var key uint16
  var card uint16
  for i := 0; i < int(containerNum); i++ {
    binary.Read(r, binary.LittleEndian, &key)
    binary.Read(r, binary.LittleEndian, &card)
    card += 1
    fmt.Println("container", i, "key", key, "card", card)
    keycards = append(keycards, KeyCard{key, card})
  }
  return keycards
}

讀取 Offset Header:

func readOffsetHeader(r io.Reader, cookie uint16, containerNum uint32) {
  if cookie == SERIAL_COOKIE_NO_RUNCONTAINER ||
    (cookie == SERIAL_COOKIE && containerNum >= NO_OFFSET_THRESHOLD) {
    // have offset header
    var offset uint32
    for i := 0; i < int(containerNum); i++ {
      binary.Read(r, binary.LittleEndian, &offset)
      fmt.Println("offset", i, offset)
    }
  }
}

讀取容器,根據類型調用不同的函數(shù):

// array
func readArrayContainer(r io.Reader, key, card uint16, bm *roaring.Bitmap) {
  var value uint16
  for i := 0; i < int(card); i++ {
    binary.Read(r, binary.LittleEndian, &value)
    bm.Add(uint32(key)<<16 | uint32(value))
  }
}
// bitmap
func readBitmapContainer(r io.Reader, key, card uint16, bm *roaring.Bitmap) {
  var u64s [1024]uint64
  for i := 0; i < 1024; i++ {
    binary.Read(r, binary.LittleEndian, &u64s[i])
  }
  bs := bitset.From(u64s[:])
  for i := uint32(0); i < 8192; i++ {
    if bs.Test(uint(i)) {
      bm.Add(uint32(key)<<16 | i)
    }
  }
}
// run
func readRunContainer(r io.Reader, key uint16, bm *roaring.Bitmap) {
  var runNum uint16
  binary.Read(r, binary.LittleEndian, &runNum)
  var startNum uint16
  var length uint16
  for i := 0; i < int(runNum); i++ {
    binary.Read(r, binary.LittleEndian, &startNum)
    binary.Read(r, binary.LittleEndian, &length)
    length += 1
    for j := uint16(0); j < length; j++ {
      bm.Add(uint32(key)<<16 | uint32(startNum+j))
    }
  }
}

整合:

func main() {
  data, err := ioutil.ReadFile("../roaring.bin")
  if err != nil {
    log.Fatal(err)
  }
  r := bytes.NewReader(data)
  cookie, containerNum, runFlagBitset := readCookieHeader(r)
  keycards := readDescriptiveHeader(r, containerNum)
  readOffsetHeader(r, cookie, containerNum)
  bm := roaring.New()
  for i := uint32(0); i < uint32(containerNum); i++ {
    if runFlagBitset != nil && runFlagBitset[i/8]&(1<<(i%8)) != 0 {
      // run
      readRunContainer(r, keycards[i].key, bm)
    } else if keycards[i].card <= 4096 {
      // array
      readArrayContainer(r, keycards[i].key, keycards[i].card, bm)
    } else {
      // bitmap
      readBitmapContainer(r, keycards[i].key, keycards[i].card, bm)
    }
  }
  fmt.Println(bm.String())
}

我將寫入讀取那個示例中的 byte.Buffer 保存到文件roaring.bin中。上面的程序就可以解析這個文件:

12346 1 []
container 0 key 0 card 8
offset 0 16
{1,3,5,7,100,300,500,700}

成功還原了位圖??

總結

本文我們首先介紹了 roaring 壓縮位圖的使用。如果不考慮內部實現(xiàn),壓縮位圖和普通的位圖在使用上并沒有多少區(qū)別。

然后我通過 8 張原理圖詳細分析了存儲的格式。

最后通過手擼一個解析來加深對原理的理解。

大家如果發(fā)現(xiàn)好玩、好用的 Go 語言庫,歡迎到 Go 每日一庫 GitHub 上提交 issue??

參考

roaring GitHub:github.com/RoaringBitmap/roaring

roaring 文件格式:https://github.com/RoaringBitmap/RoaringFormatSpec

Go 每日一庫 GitHub:https://github.com/darjun/go-daily-lib

以上就是Go壓縮位圖庫roaring安裝使用詳解的詳細內容,更多關于Go壓縮位圖庫roaring的資料請關注腳本之家其它相關文章!

相關文章

  • go sync Once實現(xiàn)原理示例解析

    go sync Once實現(xiàn)原理示例解析

    這篇文章主要為大家介紹了go sync Once實現(xiàn)原理示例解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-01-01
  • GO語言中通道和sync包的使用教程分享

    GO語言中通道和sync包的使用教程分享

    這篇文章主要為大家詳細介紹了Go語言中通道和sync包的相關資料,文中的示例代碼講解詳細,對我們學習Go語言有一定的幫助,需要的可以參考一下
    2023-02-02
  • Golang全局變量加鎖的問題解決

    Golang全局變量加鎖的問題解決

    這篇文章主要介紹了解決Golang全局變量加鎖的問題,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2021-05-05
  • mayfly-go部署和使用詳解

    mayfly-go部署和使用詳解

    這篇文章主要介紹了mayfly-go部署和使用詳解,此處部署基于CentOS7.4部署,結合實例代碼圖文給大家講解的非常詳細,需要的朋友可以參考下
    2022-09-09
  • Golang二進制文件混淆保護操作

    Golang二進制文件混淆保護操作

    這篇文章主要介紹了Golang二進制文件混淆保護操作,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-12-12
  • go實現(xiàn)thrift的網絡傳輸性能及需要注意問題示例解析

    go實現(xiàn)thrift的網絡傳輸性能及需要注意問題示例解析

    這篇文章主要為大家介紹了go實現(xiàn)thrift的網絡傳輸性能及需要注意問題示例解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-09-09
  • 淺談golang類型斷言,失敗類型斷言返回值問題

    淺談golang類型斷言,失敗類型斷言返回值問題

    這篇文章主要介紹了淺談golang類型斷言,失敗類型斷言返回值問題,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-12-12
  • GoFrame框架gset使用對比PHP?Java?Redis優(yōu)勢

    GoFrame框架gset使用對比PHP?Java?Redis優(yōu)勢

    這篇文章主要為大家介紹了GoFrame框架gset對比PHP?Java?Redis的使用優(yōu)勢詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2022-06-06
  • Golang新提案:panic?能不能加個?PanicError?

    Golang新提案:panic?能不能加個?PanicError?

    這篇文章主要為大家介紹了Golang的新提案關于panic能不能加個PanicError的問題分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-12-12
  • Go語言學習之new函數(shù)的用法詳解

    Go語言學習之new函數(shù)的用法詳解

    這篇文章主要為大家詳細介紹了Go語言中new()函數(shù)的相關知識以及具體用法,文中的示例代碼講解詳細,具有一定的學習價值,感興趣的小伙伴可以了解一下
    2023-05-05

最新評論