Go位集合相關(guān)操作bitset庫(kù)安裝使用
簡(jiǎn)介
我們都知道計(jì)算機(jī)是基于二進(jìn)制的，位運(yùn)算是計(jì)算機(jī)的基礎(chǔ)運(yùn)算。位運(yùn)算的優(yōu)勢(shì)很明顯，CPU 指令原生支持、速度快。基于位運(yùn)算的位集合在有限的場(chǎng)景中替換集合數(shù)據(jù)結(jié)構(gòu)可以收到意想不到的效果。bitset庫(kù)實(shí)現(xiàn)了位集合及相關(guān)操作，不妨拿來(lái)即用。
安裝
本文代碼使用 Go Modules。
創(chuàng)建目錄并初始化：
$ mkdir -p bitset && cd bitset $ go mod init github.com/darjun/go-daily-lib/bitset
安裝bitset庫(kù)：
$ go get -u github.com/bits-and-blooms/bitset
使用
位集合的基本操作有：
- 檢查位（Test）：檢查某個(gè)索引是否為 1。類比檢查元素是否在集合中
- 設(shè)置位（Set）：將某個(gè)索引設(shè)置為 1。類比向集合添加元素
- 清除位（Clear）：將某個(gè)索引清除，設(shè)置為 0。類比從集合中刪除元素
- 翻轉(zhuǎn)位（Flip）：如果某個(gè)索引為 1，則設(shè)置為 0，反之設(shè)置為 1
- 并（Union）：兩個(gè)位集合執(zhí)行并操作。類比集合的并
- 交（Intersection）：兩個(gè)位集合執(zhí)行交操作。類比集合的交
位集合一般用于小數(shù)值的非負(fù)整數(shù)的場(chǎng)景中。就拿游戲中簡(jiǎn)單的簽到舉例吧，很多游戲都有簽到活動(dòng)，短的有 7 天的，長(zhǎng)的有 30 天。這種就很適合使用位集合。每個(gè)位的值表示其索引位置對(duì)應(yīng)的那天有沒(méi)有簽到。
type Player struct {
sign *bitset.BitSet
}
func NewPlayer(sign uint) *Player {
return &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 <= 7; day++ {
if rand.Intn(100)&1 == 0 {
player.Sign(day - 1)
}
}
for day := uint(1); day <= 7; day++ {
if player.IsSigned(day - 1) {
fmt.Printf("day:%d signed\n", day)
}
}
}bitset 提供了多種創(chuàng)建 BitSet 對(duì)象的方法。
首先 bitset.BitSet 零值可用，如果一開(kāi)始不知道有多少元素，可以使用這種方式創(chuàng)建：
var b bitset.BitSet
BitSet 在設(shè)置時(shí)自動(dòng)調(diào)整大小。如果事先知道長(zhǎng)度，創(chuàng)建 BitSet 時(shí)可傳入此值，能有效避免自動(dòng)調(diào)整的開(kāi)銷：
b := bitset.New(100)
bitset 結(jié)構(gòu)支持鏈?zhǔn)秸{(diào)用，大部分方法返回自身的指針，所以可以這樣寫(xiě)：
b.Set(10).Set(11).Clear(12).Flip(13);
注意，bitset 的索引是從 0 開(kāi)始的。
記得之前在網(wǎng)上看過(guò)一道題：
一個(gè)農(nóng)夫帶著一只狼、一頭羊和一顆白菜來(lái)到河邊。他需要用船把他們帶到對(duì)岸。然而，這艘船只能容下農(nóng)夫本人和另外一種東西（要么是狼，要么是羊，要么是白菜）。如果農(nóng)夫不在場(chǎng)的話，狼就會(huì)吃掉羊，羊會(huì)吃掉白菜。請(qǐng)為農(nóng)夫解決這個(gè)問(wèn)題。
這其實(shí)是一個(gè)狀態(tài)搜索的問(wèn)題，用回溯法就能解決。農(nóng)夫、狼、羊、白菜都有兩個(gè)狀態(tài)，即在河左岸（假設(shè)剛開(kāi)始農(nóng)夫所處的是左岸）還是河右岸。這里實(shí)際上還有個(gè)船的狀態(tài)，由于船一定和農(nóng)夫的狀態(tài)是一致的，就不用額外考慮了。這些狀態(tài)我們很容易用位集合來(lái)表示：
const ( FARMER = iota WOLF SHEEP CABBAGE )
編寫(xiě)一個(gè)函數(shù)來(lái)判斷狀態(tài)是否合法。有兩種狀態(tài)不合法：
- 狼和羊在同一邊，并且不和農(nóng)夫在同一邊。此時(shí)狼會(huì)吃掉羊
- 羊和白菜在同一邊，并且不和農(nóng)夫在同一邊。此時(shí)羊會(huì)吃掉白菜
func IsStateValid(state *bitset.BitSet) bool {
if state.Test(WOLF) == state.Test(SHEEP) &&
state.Test(WOLF) != state.Test(FARMER) {
// 狼和羊在同一邊，并且不和農(nóng)夫在同一邊
// 狼會(huì)吃掉羊，非法
return false
}
if state.Test(SHEEP) == state.Test(CABBAGE) &&
state.Test(SHEEP) != state.Test(FARMER) {
// 羊和白菜在同一邊，并且不和農(nóng)夫在同一邊
// 羊會(huì)吃掉白菜，非法
return false
}
return true
}接下來(lái)編寫(xiě)搜索函數(shù)：
func search(b *bitset.BitSet, visited map[string]struct{}) bool {
if !IsStateValid(b) {
return false
}
if _, exist := visited[b.String()]; exist {
// 狀態(tài)已遍歷
return false
}
if b.Count() == 4 {
return true
}
visited[b.String()] = struct{}{}
for index := uint(FARMER); index <= CABBAGE; index++ {
if b.Test(index) != b.Test(FARMER) {
// 與農(nóng)夫不在一邊，不能帶上船
continue
}
// 帶到對(duì)岸去
b.Flip(index)
if index != FARMER {
// 如果 index 為 FARMER，表示不帶任何東西
b.Flip(FARMER)
}
if search(b, visited) {
return true
}
// 狀態(tài)恢復(fù)
b.Flip(index)
if index != FARMER {
b.Flip(FARMER)
}
}
return false
}主函數(shù)：
func main() {
b := bitset.New(4)
visited := make(map[string]struct{})
fmt.Println(search(b, visited))
}初始時(shí)，所有狀態(tài)為 0，都到對(duì)岸之后所有狀態(tài)為 1，故b.Count() == 4表示都已到達(dá)對(duì)岸了。由于搜索是盲目的，可能會(huì)無(wú)限循環(huán)：這次農(nóng)夫?qū)⒀驇У綄?duì)岸，下次又將其從對(duì)岸帶回來(lái)了。所以我們需要做狀態(tài)去重。bitset.String()返回當(dāng)前位集合的字符串表示，我們以此來(lái)判斷狀態(tài)是否重復(fù)。
for 循環(huán)依次嘗試帶各種物品，或什么也不帶。驅(qū)動(dòng)查找過(guò)程。
如果想得到農(nóng)夫正確的動(dòng)作序列，可以給 search 加一個(gè)參數(shù)，記錄每一步的操作：
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{"農(nóng)夫", "狼", "羊", "白菜"}
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("農(nóng)夫?qū)ⅰ?s】從河左岸帶到河右岸\n", names[index])
} else {
fmt.Printf("農(nóng)夫?qū)ⅰ?s】從河右岸帶到河左岸\n", names[index])
}
return
}
}
if !cur.Test(FARMER) {
fmt.Println("農(nóng)夫獨(dú)自從河左岸到河右岸")
} else {
fmt.Println("農(nóng)夫獨(dú)自從河右岸到河左岸")
}
}
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
}
}運(yùn)行結(jié)果：
=======================
河左岸：
農(nóng)夫
狼
羊
白菜
河右岸：
=======================
農(nóng)夫?qū)ⅰ狙颉繌暮幼蟀稁У胶佑野?br />=======================
河左岸：
狼
白菜
河右岸：
農(nóng)夫
羊
=======================
農(nóng)夫獨(dú)自從河右岸到河左岸
=======================
河左岸：
農(nóng)夫
狼
白菜
河右岸：
羊
=======================
農(nóng)夫?qū)ⅰ纠恰繌暮幼蟀稁У胶佑野?br />=======================
河左岸：
白菜
河右岸：
農(nóng)夫
狼
羊
=======================
農(nóng)夫?qū)ⅰ狙颉繌暮佑野稁У胶幼蟀?br />=======================
河左岸：
農(nóng)夫
羊
白菜
河右岸：
狼
=======================
農(nóng)夫?qū)ⅰ景撞恕繌暮幼蟀稁У胶佑野?br />=======================
河左岸：
羊
河右岸：
農(nóng)夫
狼
白菜
=======================
農(nóng)夫獨(dú)自從河右岸到河左岸
=======================
河左岸：
農(nóng)夫
羊
河右岸：
狼
白菜
=======================
農(nóng)夫?qū)ⅰ狙颉繌暮幼蟀稁У胶佑野?br />=======================
河左岸：
河右岸：
農(nóng)夫
狼
羊
白菜
=======================
即農(nóng)夫操作過(guò)程為：將羊帶到右岸->獨(dú)自返回->將白菜帶到右岸->再將羊帶回左岸->帶上狼到右岸->獨(dú)自返回->最后將羊帶到右岸->完成。
為什么要使用它？
似乎直接使用位運(yùn)算就可以了，為什么要使用 bitset 庫(kù)呢？
因?yàn)橥ㄓ茫厦媪信e的兩個(gè)例子都是很小的整數(shù)值，如果整數(shù)值超過(guò) 64 位，我們必然要通過(guò)切片來(lái)存儲(chǔ)。此時(shí)手寫(xiě)操作就非常不便了，而且容易出錯(cuò)。
庫(kù)的優(yōu)勢(shì)體現(xiàn)在：
- 足夠通用
- 持續(xù)優(yōu)化
- 大規(guī)模使用
只要對(duì)外提供的接口保持不變，它可以一直優(yōu)化內(nèi)部實(shí)現(xiàn)。雖然我們也可以做，但是費(fèi)時(shí)費(fèi)力。而且有些優(yōu)化涉及到比較復(fù)雜的算法，自己實(shí)現(xiàn)的難度較高且易錯(cuò)。
有一個(gè)很典型的例子，求一個(gè) uint64 的二進(jìn)制表示中 1 的數(shù)量（popcnt，或 population count）。實(shí)現(xiàn)的方法有很多。
最直接的，我們一位一位地統(tǒng)計(jì)：
func popcnt1(n uint64) uint64 {
var count uint64
for n > 0 {
if n&1 == 1 {
count++
}
n >>= 1
}
return count
}考慮空間換時(shí)間，我們可以預(yù)先計(jì)算 0-255 這 256 個(gè)數(shù)字的二進(jìn)制表示中 1 的個(gè)數(shù)，然后每 8 位計(jì)算一次，可能將計(jì)算次數(shù)減少到之前的 1/8。這也是標(biāo)準(zhǔn)庫(kù)中的做法：
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 庫(kù)中的算法：
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
}對(duì)以上三種實(shí)現(xiàn)進(jìn)行性能測(cè)試：
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 相對(duì) popcnt1 有 40 倍的性能提升。在學(xué)習(xí)上我們可以自己嘗試造輪子，以此來(lái)加深自己對(duì)技術(shù)的理解。但是在工程上，通常更傾向于使用穩(wěn)定的、高效的庫(kù)。
總結(jié)
本文借著 bitset 庫(kù)介紹了位集合的使用。并且應(yīng)用 bitset 解決了農(nóng)夫過(guò)河問(wèn)題。最后我們討論了為什么要使用庫(kù)？
大家如果發(fā)現(xiàn)好玩、好用的 Go 語(yǔ)言庫(kù)，歡迎到 Go 每日一庫(kù) GitHub 上提交 issue??
一點(diǎn)閑話
我發(fā)現(xiàn)人的惰性實(shí)在是太可怕了。雖然這半年來(lái)沒(méi)寫(xiě)文章一開(kāi)始是因?yàn)楣ぷ魃系脑?，后?lái)單純是因?yàn)閼T性，因?yàn)閼小６铱偸?ldquo;裝著很忙”來(lái)逃避需要花時(shí)間、花精力的事情。在這種想動(dòng)又不想動(dòng)的角逐之間，時(shí)間就這么一晃而過(guò)。
我們總是在抱怨沒(méi)有時(shí)間，沒(méi)有時(shí)間。但仔細(xì)想想，仔細(xì)算算，我們花在刷短視頻，玩游戲上的時(shí)間其實(shí)并不少。
上周我在阮一峰老師的周刊上看到一篇文章《人生不短》，看了之后深有觸動(dòng)。人總該有所堅(jiān)持，生活才有意義。
參考
- bitset GitHub：github.com/bits-and-blooms/bitset
- Go 每日一庫(kù) GitHub：https://github.com/darjun/go-daily-lib
以上就是Go位集合相關(guān)操作bitset庫(kù)安裝使用的詳細(xì)內(nèi)容，更多關(guān)于Go位集合bitset庫(kù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
本文主要介紹了Go之集合slice的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
基于golang如何實(shí)現(xiàn)error工具包詳解
Go 語(yǔ)言使用 error 類型來(lái)返回函數(shù)執(zhí)行過(guò)程中遇到的錯(cuò)誤，下面這篇文章主要給大家介紹了關(guān)于如何基于golang實(shí)現(xiàn)error工具包的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下2018-09-09
go mutex互斥鎖使用Lock和Unlock方法占有釋放資源
Go號(hào)稱是為了高并發(fā)而生的,在高并發(fā)場(chǎng)景下,勢(shì)必會(huì)涉及到對(duì)公共資源的競(jìng)爭(zhēng),當(dāng)對(duì)應(yīng)場(chǎng)景發(fā)生時(shí),我們經(jīng)常會(huì)使用 mutex 的 Lock() 和 Unlock() 方法來(lái)占有或釋放資源,雖然調(diào)用簡(jiǎn)單,但 mutex 的內(nèi)部卻涉及挺多的,本文來(lái)好好研究一下2023-09-09
GoFrame框架數(shù)據(jù)校驗(yàn)之校驗(yàn)結(jié)果Error接口對(duì)象
這篇文章主要為大家介紹了GoFrame框架數(shù)據(jù)校驗(yàn)之校驗(yàn)結(jié)果Error接口對(duì)象示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-06-06
這篇文章主要為大家詳細(xì)介紹了使用Golang實(shí)現(xiàn)流式輸出的相關(guān)知識(shí),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2025-03-03
golang雪花算法實(shí)現(xiàn)64位的ID的示例代碼
本文展示了使用Go語(yǔ)言實(shí)現(xiàn)雪花算法生成64位ID的示例代碼,雪花算法通過(guò)當(dāng)前時(shí)間戳、工作節(jié)點(diǎn)ID、數(shù)據(jù)中心ID和序列號(hào)生成唯一的64位ID,確保在分布式系統(tǒng)中的唯一性和時(shí)間順序性,感興趣的可以了解一下2024-09-09
這篇文章主要為大家介紹了Go Java算法之累加數(shù)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-08-08
golang強(qiáng)制類型轉(zhuǎn)換和類型斷言
這篇文章主要介紹了詳情介紹golang類型轉(zhuǎn)換問(wèn)題,分別由介紹類型斷言和類型轉(zhuǎn)換，這兩者都是不同的概念，下面文章圍繞類型斷言和類型轉(zhuǎn)換的相關(guān)資料展開(kāi)文章的詳細(xì)內(nèi)容,需要的朋友可以參考以下2021-12-12
在學(xué)習(xí)操作系統(tǒng)的時(shí)候，我們應(yīng)該都學(xué)習(xí)過(guò)臨界區(qū)、互斥鎖這些概念，用于在并發(fā)環(huán)境下保證狀態(tài)的正確性。在?Go語(yǔ)言?里面互斥鎖是?sync.Mutex?，我們本篇文章就來(lái)學(xué)習(xí)下為什么要使用互斥鎖、如何使用互斥鎖，以及使用時(shí)的常見(jiàn)問(wèn)題2022-10-10
這篇文章主要介紹了go語(yǔ)言template用法,實(shí)例分析了template的使用技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-02-02