Golang?中實(shí)現(xiàn)?Set的思路詳解
在Go編程中,數(shù)據(jù)結(jié)構(gòu)的選擇對解決問題至關(guān)重要。本文將探討如何在 GO 中實(shí)現(xiàn) set 和 bitset 兩種數(shù)據(jù)結(jié)構(gòu),以及它們在Go中的應(yīng)用場景。
Go 的數(shù)據(jù)結(jié)構(gòu)
Go 內(nèi)置的數(shù)據(jù)結(jié)構(gòu)并不多。工作中,我們最常用的兩種數(shù)據(jù)結(jié)構(gòu)分別是 slice 和 map,即切片和映射。 其實(shí),Go 中也有數(shù)組,切片的底層就是數(shù)組,只不過因?yàn)榍衅拇嬖冢覀兤綍r很少使用它。
除了 Go 內(nèi)置的數(shù)據(jù)結(jié)構(gòu),還有一些數(shù)據(jù)結(jié)構(gòu)是由 Go 的官方 container 包提供,如 heap 堆、list 雙向鏈表和ring 回環(huán)鏈表。但今天我們不講它們,這些數(shù)據(jù)結(jié)構(gòu),對于熟手來說,看看文檔就會使用了。
我們今天將來聊的是 set 和 bitset。據(jù)我所知,其他一些語言,比如 Java,是有這兩種數(shù)據(jù)結(jié)構(gòu)。但 Go 當(dāng)前還沒有以任何形式提供。
實(shí)現(xiàn)思路
先來看一篇文章,訪問地址 2 basic set implementations 閱讀。文中介紹了兩種 go 實(shí)現(xiàn) set 的思路, 分別是 map 和 bitset。
有興趣可以讀讀這篇文章,我們接下來具體介紹下。
map
我們知道,map 的 key 肯定是唯一的,而這恰好與 set 的特性一致,天然保證 set 中成員的唯一性。而且通過 map 實(shí)現(xiàn) set,在檢查是否存在某個元素時可直接使用 _, ok := m[key]
的語法,效率高。
先來看一個簡單的實(shí)現(xiàn),如下:
set := make(map[string]bool) // New empty set set["Foo"] = true // Add for k := range set { // Loop fmt.Println(k) } delete(set, "Foo") // Delete size := len(set) // Size exists := set["Foo"] // Membership
通過創(chuàng)建 map[string]bool 來存儲 string 的集合,比較容易理解。但這里還有個問題,map 的 value 是布爾類型,這會導(dǎo)致 set 多占一定內(nèi)存空間,而 set 不該有這個問題。
怎么解決這個問題?
設(shè)置 value 為空結(jié)構(gòu)體,在 Go 中,空結(jié)構(gòu)體不占任何內(nèi)存。當(dāng)然,如果不確定,也可以來證明下這個結(jié)論。
unsafe.Sizeof(struct{}{}) // 結(jié)果為 0
優(yōu)化后的代碼,如下:
type void struct{} var member void set := make(map[string]void) // New empty set set["Foo"] = member // Add for k := range set { // Loop fmt.Println(k) } delete(set, "Foo") // Delete size := len(set) // Size _, exists := set["Foo"] // Membership
之前在網(wǎng)上看到有人按這個思路做了封裝,還寫了一篇文章,可以去讀一下。
其實(shí),github 上已經(jīng)有個成熟的包,名為 golang-set,它也是采用這個思路實(shí)現(xiàn)的。訪問地址 golang-set,描述中說 Docker 用的也是它。包中提供了兩種 set 實(shí)現(xiàn),線程安全的 set 和非線程安全的 set。
演示一個簡單的案例。
package main import ( "fmt" mapset "github.com/deckarep/golang-set" ) func main() { // 默認(rèn)創(chuàng)建的線程安全的,如果無需線程安全 // 可以使用 NewThreadUnsafeSet 創(chuàng)建,使用方法都是一樣的。 s1 := mapset.NewSet(1, 2, 3, 4) fmt.Println("s1 contains 3: ", s1.Contains(3)) fmt.Println("s1 contains 5: ", s1.Contains(5)) // interface 參數(shù),可以傳遞任意類型 s1.Add("poloxue") fmt.Println("s1 contains poloxue: ", s1.Contains("poloxue")) s1.Remove(3) fmt.Println("s1 contains 3: ", s1.Contains(3)) s2 := mapset.NewSet(1, 3, 4, 5) // 并集 fmt.Println(s1.Union(s2)) }
輸出如下:
s1 contains 3: true
s1 contains 5: false
s1 contains poloxue: true
s1 contains 3: false
Set{4, polxue, 1, 2, 3, 5}
例子中演示了簡單的使用方式,如果有不明白的,看下源碼,這些數(shù)據(jù)結(jié)構(gòu)的操作方法名都是很常見的,比如交集 Intersect、差集 Difference 等,一看就懂。
bitset
繼續(xù)聊聊 bitset,bitset 中每個數(shù)子用一個 bit 即能表示,對于一個 int8 的數(shù)字,我們可以用它表示 8 個數(shù)字,能幫助我們大大節(jié)省數(shù)據(jù)的存儲空間。
bitset 最常見的應(yīng)用有 bitmap 和 flag,即位圖和標(biāo)志位。這里,我們先嘗試用它表示一些操作的標(biāo)志位。比如某個場景,我們需要三個 flag 分別表示權(quán)限1、權(quán)限2和權(quán)限3,而且?guī)讉€權(quán)限可以共存。我們可以分別用三個常量 F1、F2、F3 表示位 Mask。
示例代碼如下(引用自文章 Bitmasks, bitsets and flags):
type Bits uint8 const ( F0 Bits = 1 << iota F1 F2 ) func Set(b, flag Bits) Bits { return b | flag } func Clear(b, flag Bits) Bits { return b &^ flag } func Toggle(b, flag Bits) Bits { return b ^ flag } func Has(b, flag Bits) bool { return b&flag != 0 } func main() { var b Bits b = Set(b, F0) b = Toggle(b, F2) for i, flag := range []Bits{F0, F1, F2} { fmt.Println(i, Has(b, flag)) } }
例子中,我們本來需要三個數(shù)才能表示這三個標(biāo)志,但現(xiàn)在通過一個 uint8 就可以。bitset 的一些操作,如設(shè)置 Set、清除 Clear、切換 Toggle、檢查 Has 通過位運(yùn)算就可以實(shí)現(xiàn),而且非常高效。
bitset 對集合操作有著天然的優(yōu)勢,直接通過位運(yùn)算符便可實(shí)現(xiàn)。比如交集、并集、和差集,示例如下:
- 交集:a & b
- 并集:a | b
- 差集:a & (~b)
底層的語言、庫、框架常會使用這種方式設(shè)置標(biāo)志位。
以上的例子中只展示了少量數(shù)據(jù)的處理方式,uint8 占 8 bit 空間,只能表示 8 個數(shù)字。那大數(shù)據(jù)場景能否可以使用這套思路呢?
我們可以把 bitset 和 Go 中的切片結(jié)合起來,重新定義 Bits 類型,如下:
type Bitset struct { data []int64 }
但如此也會產(chǎn)生一些問題,設(shè)置 bit,我們怎么知道它在哪里呢?仔細(xì)想想,這個位置信息包含兩部分,即保存該 bit 的數(shù)在切片索引位置和該 bit 在數(shù)字中的哪位,分別將它們命名為 index 和 position。那怎么獲???
index 可以通過整除獲取,比如我們想知道表示 65 的 bit 在切片的哪個 index,通過 65 / 64 即可獲得,如果為了高效,也可以用位運(yùn)算實(shí)現(xiàn),即用移位替換除法,比如 65 >> 6,6 表示移位偏移,即 2^n = 64 的 n。
postion 是除法的余數(shù),我們可以通過模運(yùn)算獲得,比如 65 % 64 = 1,同樣為了效率,也有相應(yīng)的位運(yùn)算實(shí)現(xiàn),比如 65 & 0b00111111,即 65 & 63。
一個簡單例子,如下:
package main import ( "fmt" ) const ( shift = 6 mask = 0x3f // 即0b00111111 ) type Bitset struct { data []int64 } func NewBitSet(n int) *Bitset { // 獲取位置信息 index := n >> shift set := &Bitset{ data: make([]int64, index+1), } // 根據(jù) n 設(shè)置 bitset set.data[index] |= 1 << uint(n&mask) return set } func (set *Bitset) Contains(n int) bool { // 獲取位置信息 index := n >> shift return set.data[index]&(1<<uint(n&mask)) != 0 } func main() { set := NewBitSet(65) fmt.Println("set contains 65", set.Contains(65)) fmt.Println("set contains 64", set.Contains(64)) }
輸出結(jié)果
set contains 65 true
set contains 64 false
以上的例子功能很簡單,只是為了演示,只有創(chuàng)建 bitset 和 contains 兩個功能,其他諸如添加、刪除、不同 bitset 間的交、并、差還沒有實(shí)現(xiàn)。有興趣的朋友可以繼續(xù)嘗試。
其實(shí),bitset 包也有人實(shí)現(xiàn)了,github地址 bit??梢宰x讀它的源碼,實(shí)現(xiàn)思路和上面介紹差不多。
下面是一個使用案例。
package main import ( "fmt" "github.com/yourbasic/bit" ) func main() { s := bit.New(2, 3, 4, 65, 128) fmt.Println("s contains 65", s.Contains(65)) fmt.Println("s contains 15", s.Contains(15)) s.Add(15) fmt.Println("s contains 15", s.Contains(15)) fmt.Println("next 20 is ", s.Next(20)) fmt.Println("prev 20 is ", s.Prev(20)) s2 := bit.New(10, 22, 30) s3 := s.Or(s2) fmt.Println("next 20 is ", s3.Next(20)) s3.Visit(func(n int) bool { fmt.Println(n) return false // 返回 true 表示終止遍歷 }) }
執(zhí)行結(jié)果:
s contains 65 true
s contains 15 false
s contains 15 true
next 20 is 65
prev 20 is 15
next 20 is 22
2
3
4
10
15
22
30
65
128
代碼的意思很好理解,就是一些增刪改查和集合的操作。要注意的是,bitset 和前面的 set 的區(qū)別,bitset 的成員只能是 int 整型,沒有 set 靈活。平時的使用場景也比較少,主要用在對效率和存儲空間要求較高的場景。
總結(jié)
本文介紹了Go 中兩種 set 的實(shí)現(xiàn)原理,并在此基礎(chǔ)介紹了對應(yīng)于它們的兩個包簡單使用。我覺得,通過這篇文章,Go 中 set 的使用,基本都可以搞定了。
除這兩個包,再補(bǔ)充兩個,zoumo/goset 和 github.com/willf/bitset。
博文地址:Golang 中如何實(shí)現(xiàn) Set
到此這篇關(guān)于Golang 中實(shí)現(xiàn) Set的思路詳解的文章就介紹到這了,更多相關(guān)Golang Set內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Go關(guān)鍵字defer的使用和底層實(shí)現(xiàn)
defer是Go語言的關(guān)鍵字,一般用于資源的釋放和異常的捕捉,defer語句后將其后面跟隨的語句進(jìn)行延遲處理,就是說在函數(shù)執(zhí)行完畢后再執(zhí)行調(diào)用,也就是return的ret指令之前,本文給大家介紹了Go關(guān)鍵字defer的使用和底層實(shí)現(xiàn),需要的朋友可以參考下2023-11-11Go語言之重要數(shù)組類型切片(slice)make,append函數(shù)解讀
這篇文章主要介紹了Go語言之重要數(shù)組類型切片(slice)make,append函數(shù)用法,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-09-09Go語言copy()實(shí)現(xiàn)切片復(fù)制
本文主要介紹了Go語言copy()實(shí)現(xiàn)切片復(fù)制,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04go語言csrf庫使用實(shí)現(xiàn)原理示例解析
這篇文章主要為大家介紹了go語言csrf庫使用實(shí)現(xiàn)原理示例解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-10-10