網站首頁編程語言正文

Go位集合相關操作bitset庫安裝使用_Golang

作者：darjun ? 更新時間： 2022-09-15 編程語言

簡介

我們都知道計算機是基于二進制的，位運算是計算機的基礎運算。位運算的優勢很明顯，CPU 指令原生支持、速度快。基于位運算的位集合在有限的場景中替換集合數據結構可以收到意想不到的效果。bitset庫實現了位集合及相關操作，不妨拿來即用。

安裝

本文代碼使用 Go Modules。

創建目錄并初始化：

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

安裝bitset庫：

$ go get -u github.com/bits-and-blooms/bitset

使用

位集合的基本操作有：

檢查位（Test）：檢查某個索引是否為 1。類比檢查元素是否在集合中
設置位（Set）：將某個索引設置為 1。類比向集合添加元素
清除位（Clear）：將某個索引清除，設置為 0。類比從集合中刪除元素
翻轉位（Flip）：如果某個索引為 1，則設置為 0，反之設置為 1
并（Union）：兩個位集合執行并操作。類比集合的并
交（Intersection）：兩個位集合執行交操作。類比集合的交

位集合一般用于小數值的非負整數的場景中。就拿游戲中簡單的簽到舉例吧，很多游戲都有簽到活動，短的有 7 天的，長的有 30 天。這種就很適合使用位集合。每個位的值表示其索引位置對應的那天有沒有簽到。

type Player struct {
  sign *bitset.BitSet
}
func NewPlayer(sign uint) *Player {
  return &amp;Player{
    sign: bitset.From([]uint64{uint64(sign)}),
  }
}
func (this *Player) Sign(day uint) {
  this.sign.Set(day)
}
func (this *Player) IsSigned(day uint) bool {
  return this.sign.Test(day)
}
func main() {
  player := NewPlayer(1) // 第一天簽到
  for day := uint(2); day &lt;= 7; day++ {
    if rand.Intn(100)&amp;1 == 0 {
      player.Sign(day - 1)
    }
  }
  for day := uint(1); day &lt;= 7; day++ {
    if player.IsSigned(day - 1) {
      fmt.Printf("day:%d signed\n", day)
    }
  }
}

bitset 提供了多種創建 BitSet 對象的方法。

首先 bitset.BitSet 零值可用，如果一開始不知道有多少元素，可以使用這種方式創建：

var b bitset.BitSet

BitSet 在設置時自動調整大小。如果事先知道長度，創建 BitSet 時可傳入此值，能有效避免自動調整的開銷：

b := bitset.New(100)

bitset 結構支持鏈式調用，大部分方法返回自身的指針，所以可以這樣寫：

b.Set(10).Set(11).Clear(12).Flip(13);

注意，bitset 的索引是從 0 開始的。

記得之前在網上看過一道題：

一個農夫帶著一只狼、一頭羊和一顆白菜來到河邊。他需要用船把他們帶到對岸。然而，這艘船只能容下農夫本人和另外一種東西（要么是狼，要么是羊，要么是白菜）。如果農夫不在場的話，狼就會吃掉羊，羊會吃掉白菜。請為農夫解決這個問題。

這其實是一個狀態搜索的問題，用回溯法就能解決。農夫、狼、羊、白菜都有兩個狀態，即在河左岸（假設剛開始農夫所處的是左岸）還是河右岸。這里實際上還有個船的狀態，由于船一定和農夫的狀態是一致的，就不用額外考慮了。這些狀態我們很容易用位集合來表示：

const (
  FARMER = iota
  WOLF
  SHEEP
  CABBAGE
)

編寫一個函數來判斷狀態是否合法。有兩種狀態不合法：

狼和羊在同一邊，并且不和農夫在同一邊。此時狼會吃掉羊
羊和白菜在同一邊，并且不和農夫在同一邊。此時羊會吃掉白菜

func IsStateValid(state *bitset.BitSet) bool {
  if state.Test(WOLF) == state.Test(SHEEP) &amp;&amp;
    state.Test(WOLF) != state.Test(FARMER) {
    // 狼和羊在同一邊，并且不和農夫在同一邊
    // 狼會吃掉羊，非法
    return false
  }
  if state.Test(SHEEP) == state.Test(CABBAGE) &amp;&amp;
    state.Test(SHEEP) != state.Test(FARMER) {
    // 羊和白菜在同一邊，并且不和農夫在同一邊
    // 羊會吃掉白菜，非法
    return false
  }
  return true
}

接下來編寫搜索函數：

func search(b *bitset.BitSet, visited map[string]struct{}) bool {
  if !IsStateValid(b) {
    return false
  }
  if _, exist := visited[b.String()]; exist {
    // 狀態已遍歷
    return false
  }
  if b.Count() == 4 {
    return true
  }
  visited[b.String()] = struct{}{}
  for index := uint(FARMER); index &lt;= CABBAGE; index++ {
    if b.Test(index) != b.Test(FARMER) {
      // 與農夫不在一邊，不能帶上船
      continue
    }
    // 帶到對岸去
    b.Flip(index)
    if index != FARMER {
      // 如果 index 為 FARMER，表示不帶任何東西
      b.Flip(FARMER)
    }
    if search(b, visited) {
      return true
    }
    // 狀態恢復
    b.Flip(index)
    if index != FARMER {
      b.Flip(FARMER)
    }
  }
  return false
}

主函數：

func main() {
  b := bitset.New(4)
  visited := make(map[string]struct{})
  fmt.Println(search(b, visited))
}

初始時，所有狀態為 0，都到對岸之后所有狀態為 1，故b.Count() == 4表示都已到達對岸了。由于搜索是盲目的，可能會無限循環：這次農夫將羊帶到對岸，下次又將其從對岸帶回來了。所以我們需要做狀態去重。bitset.String()返回當前位集合的字符串表示，我們以此來判斷狀態是否重復。

for 循環依次嘗試帶各種物品，或什么也不帶。驅動查找過程。

如果想得到農夫正確的動作序列，可以給 search 加一個參數，記錄每一步的操作：

func search(b *bitset.BitSet, visited map[string]struct{}, path *[]*bitset.BitSet) bool {
  // 記錄路徑
  *path = append(*path, b.Clone())
  if b.Count() == 4 {
    return true
  }
  // ...
  *path = (*path)[:len(*path)-1]
  return false
}
func main() {
  b := bitset.New(4)
  visited := make(map[string]struct{})
  var path []*bitset.BitSet
  if search(b, visited, &path) {
    PrintPath(path)
  }
}

如果找到解，打印之：

var names = []string{"農夫", "狼", "羊", "白菜"}
func PrintState(b *bitset.BitSet) {
  fmt.Println("=======================")
  fmt.Println("河左岸：")
  for index := uint(FARMER); index <= CABBAGE; index++ {
    if !b.Test(index) {
      fmt.Println(names[index])
    }
  }
  fmt.Println("河右岸：")
  for index := uint(FARMER); index <= CABBAGE; index++ {
    if b.Test(index) {
      fmt.Println(names[index])
    }
  }
  fmt.Println("=======================")
}
func PrintMove(cur, next *bitset.BitSet) {
  for index := uint(WOLF); index <= CABBAGE; index++ {
    if cur.Test(index) != next.Test(index) {
      if !cur.Test(FARMER) {
        fmt.Printf("農夫將【%s】從河左岸帶到河右岸\n", names[index])
      } else {
        fmt.Printf("農夫將【%s】從河右岸帶到河左岸\n", names[index])
      }
      return
    }
  }
  if !cur.Test(FARMER) {
    fmt.Println("農夫獨自從河左岸到河右岸")
  } else {
    fmt.Println("農夫獨自從河右岸到河左岸")
  }
}
func PrintPath(path []*bitset.BitSet) {
  cur := path[0]
  PrintState(cur)
  for i := 1; i < len(path); i++ {
    next := path[i]
    PrintMove(cur, next)
    PrintState(next)
    cur = next
  }
}

運行結果：

=======================
河左岸：
農夫
狼
羊
白菜

河右岸：
=======================
農夫將【羊】從河左岸帶到河右岸
=======================
河左岸：
狼
白菜

河右岸：
農夫
羊
=======================
農夫獨自從河右岸到河左岸
=======================
河左岸：
農夫
狼
白菜

河右岸：
羊
=======================
農夫將【狼】從河左岸帶到河右岸
=======================
河左岸：
白菜

河右岸：
農夫
狼
羊
=======================
農夫將【羊】從河右岸帶到河左岸
=======================
河左岸：
農夫
羊
白菜

河右岸：
狼
=======================
農夫將【白菜】從河左岸帶到河右岸
=======================
河左岸：
羊

河右岸：
農夫
狼
白菜
=======================
農夫獨自從河右岸到河左岸
=======================
河左岸：
農夫
羊

河右岸：
狼
白菜
=======================
農夫將【羊】從河左岸帶到河右岸
=======================
河左岸：

河右岸：
農夫
狼
羊
白菜
=======================

即農夫操作過程為：將羊帶到右岸->獨自返回->將白菜帶到右岸->再將羊帶回左岸->帶上狼到右岸->獨自返回->最后將羊帶到右岸->完成。

為什么要使用它？

似乎直接使用位運算就可以了，為什么要使用 bitset 庫呢？

因為通用，上面列舉的兩個例子都是很小的整數值，如果整數值超過 64 位，我們必然要通過切片來存儲。此時手寫操作就非常不便了，而且容易出錯。

庫的優勢體現在：

足夠通用
持續優化
大規模使用

只要對外提供的接口保持不變，它可以一直優化內部實現。雖然我們也可以做，但是費時費力。而且有些優化涉及到比較復雜的算法，自己實現的難度較高且易錯。

有一個很典型的例子，求一個 uint64 的二進制表示中 1 的數量（popcnt，或 population count）。實現的方法有很多。

最直接的，我們一位一位地統計：

func popcnt1(n uint64) uint64 {
  var count uint64
  for n > 0 {
    if n&1 == 1 {
      count++
    }
    n >>= 1
  }
  return count
}

考慮空間換時間，我們可以預先計算 0-255 這 256 個數字的二進制表示中 1 的個數，然后每 8 位計算一次，可能將計算次數減少到之前的 1/8。這也是標準庫中的做法：

const pop8tab = "" +
  "\x00\x01\x01\x02\x01\x02\x02\x03\x01\x02\x02\x03\x02\x03\x03\x04" +
  "\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05" +
  "\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05" +
  "\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06" +
  "\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05" +
  "\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06" +
  "\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06" +
  "\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07" +
  "\x01\x02\x02\x03\x02\x03\x03\x04\x02\x03\x03\x04\x03\x04\x04\x05" +
  "\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06" +
  "\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06" +
  "\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07" +
  "\x02\x03\x03\x04\x03\x04\x04\x05\x03\x04\x04\x05\x04\x05\x05\x06" +
  "\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07" +
  "\x03\x04\x04\x05\x04\x05\x05\x06\x04\x05\x05\x06\x05\x06\x06\x07" +
  "\x04\x05\x05\x06\x05\x06\x06\x07\x05\x06\x06\x07\x06\x07\x07\x08"
func popcnt2(n uint64) uint64 {
  var count uint64
  for n > 0 {
    count += uint64(pop8tab[n&0xff])
    n >>= 8
  }
  return count
}

最后是 bitset 庫中的算法：

func popcnt3(x uint64) (n uint64) {
  x -= (x >> 1) & 0x5555555555555555
  x = (x>>2)&0x3333333333333333 + x&0x3333333333333333
  x += x >> 4
  x &= 0x0f0f0f0f0f0f0f0f
  x *= 0x0101010101010101
  return x >> 56
}

對以上三種實現進行性能測試：

goos: windows
goarch: amd64
pkg: github.com/darjun/go-daily-lib/bitset/popcnt
cpu: Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
BenchmarkPopcnt1-8         52405             24409 ns/op
BenchmarkPopcnt2-8        207452              5443 ns/op
BenchmarkPopcnt3-8       1777320               602 ns/op
PASS
ok      github.com/darjun/go-daily-lib/bitset/popcnt    4.697s

popcnt3 相對 popcnt1 有 40 倍的性能提升。在學習上我們可以自己嘗試造輪子，以此來加深自己對技術的理解。但是在工程上，通常更傾向于使用穩定的、高效的庫。

總結

本文借著 bitset 庫介紹了位集合的使用。并且應用 bitset 解決了農夫過河問題。最后我們討論了為什么要使用庫？

大家如果發現好玩、好用的 Go 語言庫，歡迎到 Go 每日一庫 GitHub 上提交 issue??

一點閑話

我發現人的惰性實在是太可怕了。雖然這半年來沒寫文章一開始是因為工作上的原因，后來單純是因為慣性，因為懶。而且總是“裝著很忙”來逃避需要花時間、花精力的事情。在這種想動又不想動的角逐之間，時間就這么一晃而過。

我們總是在抱怨沒有時間，沒有時間。但仔細想想，仔細算算，我們花在刷短視頻，玩游戲上的時間其實并不少。

上周我在阮一峰老師的周刊上看到一篇文章《人生不短》，看了之后深有觸動。人總該有所堅持，生活才有意義。

參考

bitset GitHub：github.com/bits-and-blooms/bitset
Go 每日一庫 GitHub：https://github.com/darjun/go-daily-lib

原文鏈接：https://segmentfault.com/a/1190000042181183

上一篇：Python?torch.onnx.export用法詳細介紹
下一篇：C++中的整形字節數_C 語言

日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

網站首頁編程語言正文

Go位集合相關操作bitset庫安裝使用_Golang

目錄

簡介

安裝

使用

為什么要使用它？

總結

一點閑話

參考

相關推薦

日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

網站首頁 編程語言 正文

Go位集合相關操作bitset庫安裝使用_Golang

目錄

簡介

安裝

使用

為什么要使用它？

總結

一點閑話

參考

相關推薦

網站首頁編程語言正文