Go 的數據結構


Go 內置的數據結構并不多。工作中,我們最常用的兩種數據結構分別是" />

Go中如何使用set的方法示例

 更新時間:2020-01-15 16:01:55   作者:佚名   我要評論(0)

今天來聊一下 Go 如何使用 set,本文將會涉及 set 和 bitset 兩種數據結構。
Go 的數據結構


Go 內置的數據結構并不多。工作中,我們最常用的兩種數據結構分別是

今天來聊一下 Go 如何使用 set,本文將會涉及 set 和 bitset 兩種數據結構。

Go 的數據結構

Go 內置的數據結構并不多。工作中,我們最常用的兩種數據結構分別是 slice 和 map,即切片和映射。其實,Go 中也有數組,切片的底層就是數組,只不過因為切片的存在,我們平時很少使用它。

除了 Go 內置的數據結構,還有一些數據結構是由 Go 的官方 container 包提供,如 heap 堆、list 雙向鏈表和ring 回環鏈表。但今天我們不講它們,這些數據結構,對于熟手來說,看看文檔就會使用了。

我們今天將來聊的是 set 和 bitset。據我所知,其他一些語言,比如 Java,是有這兩種數據結構。但 Go 當前還沒有以任何形式提供。

實現思路

先來看一篇文章,訪問地址 2 basic set implementations[1] 閱讀。文中介紹了兩種 go 實現 set 的思路, 分別是 map 和 bitset。

有興趣可以讀讀這篇文章,我們接下來具體介紹下。

map

我們知道,map 的 key 肯定是唯一的,而這恰好與 set 的特性一致,天然保證 set 中成員的唯一性。而且通過 map 實現 set,在檢查是否存在某個元素時可直接使用 _, ok := m[key] 的語法,效率高。

先來看一個簡單的實現,如下:

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

通過創建 map[string]bool 來存儲 string 的集合,比較容易理解。但這里還有個問題,map 的 value 是布爾類型,這會導致 set 多占一定內存空間,而 set 不該有這個問題。

怎么解決這個問題?

設置 value 為空結構體,在 Go 中,空結構體不占任何內存。當然,如果不確定,也可以來證明下這個結論。

unsafe.Sizeof(struct{}{}) // 結果為 0

優化后的代碼,如下:

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

之前在網上看到有人按這個思路做了封裝,還寫了一篇文章[2],可以去讀一下。

其實,github 上已經有個成熟的包,名為 golang-set,它也是采用這個思路實現的。訪問地址 golang-set[3],描述中說 Docker 用的也是它。包中提供了兩種 set 實現,線程安全的 set 和非線程安全的 set。

演示一個簡單的案例。

package main

import (
 "fmt"

 mapset "github.com/deckarep/golang-set"
)

func main() {
 // 默認創建的線程安全的,如果無需線程安全
 // 可以使用 NewThreadUnsafeSet 創建,使用方法都是一樣的。
 s1 := mapset.NewSet(1, 2, 3, 4)
 fmt.Println("s1 contains 3: ", s1.Contains(3))
 fmt.Println("s1 contains 5: ", s1.Contains(5))

 // interface 參數,可以傳遞任意類型
 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}

例子中演示了簡單的使用方式,如果有不明白的,看下源碼,這些數據結構的操作方法名都是很常見的,比如交集 Intersect、差集 Difference 等,一看就懂。

bitset

繼續聊聊 bitset,bitset 中每個數子用一個 bit 即能表示,對于一個 int8 的數字,我們可以用它表示 8 個數字,能幫助我們大大節省數據的存儲空間。

bitset 最常見的應用有 bitmap 和 flag,即位圖和標志位。這里,我們先嘗試用它表示一些操作的標志位。比如某個場景,我們需要三個 flag 分別表示權限1、權限2和權限3,而且幾個權限可以共存。我們可以分別用三個常量 F1、F2、F3 表示位 Mask。

示例代碼如下(引用自文章 Bitmasks, bitsets and flags[4]):

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))
 }
}

例子中,我們本來需要三個數才能表示這三個標志,但現在通過一個 uint8 就可以。bitset 的一些操作,如設置 Set、清除 Clear、切換 Toggle、檢查 Has 通過位運算就可以實現,而且非常高效。

bitset 對集合操作有著天然的優勢,直接通過位運算符便可實現。比如交集、并集、和差集,示例如下:

  • 交集:a & b
  • 并集:a | b
  • 差集:a & (~b)

底層的語言、庫、框架常會使用這種方式設置標志位。

以上的例子中只展示了少量數據的處理方式,uint8 占 8 bit 空間,只能表示 8 個數字。那大數據場景能否可以使用這套思路呢?

我們可以把 bitset 和 Go 中的切片結合起來,重新定義 Bits 類型,如下:

type Bitset struct {
 data []int64
}

但如此也會產生一些問題,設置 bit,我們怎么知道它在哪里呢?仔細想想,這個位置信息包含兩部分,即保存該 bit 的數在切片索引位置和該 bit 在數字中的哪位,分別將它們命名為 index 和 position。那怎么獲取?

index 可以通過整除獲取,比如我們想知道表示 65 的 bit 在切片的哪個 index,通過 65 / 64 即可獲得,如果為了高效,也可以用位運算實現,即用移位替換除法,比如 65 >> 6,6 表示移位偏移,即 2^n = 64 的 n。

postion 是除法的余數,我們可以通過模運算獲得,比如 65 % 64 = 1,同樣為了效率,也有相應的位運算實現,比如 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),
 }

 // 根據 n 設置 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))
}

輸出結果

set contains 65 true
set contains 64 false

以上的例子功能很簡單,只是為了演示,只有創建 bitset 和 contains 兩個功能,其他諸如添加、刪除、不同 bitset 間的交、并、差還沒有實現。有興趣的朋友可以繼續嘗試。

其實,bitset 包也有人實現了,github地址 bit[5]。可以讀讀它的源碼,實現思路和上面介紹差不多。

下面是一個使用案例。

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 表示終止遍歷
 })
}

執行結果:

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 的區別,bitset 的成員只能是 int 整型,沒有 set 靈活。平時的使用場景也比較少,主要用在對效率和存儲空間要求較高的場景。

總結

本文介紹了Go 中兩種 set 的實現原理,并在此基礎介紹了對應于它們的兩個包簡單使用。我覺得,通過這篇文章,Go 中 set 的使用,基本都可以搞定了。

除這兩個包,再補充兩個,zoumo/goset[6] 和 github.com/willf/bitset[7]。

參考資料

[1]2 basic set implementations: https://yourbasic.org/golang/implement-set/

[2]一篇文章: https://www.jb51.net/article/170043.htm

[3]golang-set: https://github.com/deckarep/golang-set

[4]Bitmasks, bitsets and flags: https://yourbasic.org/golang/bitmask-flag-set-clear/

[5]bit: https://github.com/yourbasic/bit

[6]zoumo/goset: https://github.com/zoumo/goset

[7]github.com/willf/bitset: https://github.com/willf/bitset

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。

您可能感興趣的文章:

  • Go語言中的Array、Slice、Map和Set使用詳解
  • 詳解Go中Set的實現方式
  • Go語言之自定義集合Set

相關文章

  • Go中如何使用set的方法示例

    Go中如何使用set的方法示例

    今天來聊一下 Go 如何使用 set,本文將會涉及 set 和 bitset 兩種數據結構。 Go 的數據結構 Go 內置的數據結構并不多。工作中,我們最常用的兩種數據結構分別是
    2020-01-15
  • ./ 和 sh 的使用區別詳解

    ./ 和 sh 的使用區別詳解

    ./ 和 sh的使用區別 1、使用“./”執行腳本,對應的xxx.sh腳本必須要有執行權限; 2、使用“sh” 執行腳本,對應的xxx.sh沒有執行權限,亦可執行; 3
    2020-01-15
  • win10下如何運行.sh文件的實現步驟

    win10下如何運行.sh文件的實現步驟

    確保您使用至少是Windows10的14316版本。 這種方法只適用于64位版本的Windows 10 今天居然驚奇地發現原來win10的功能簡直強大到沒話說,居然在更新后有一個Linux的子
    2020-01-15
  • Shell腳本之Expect免交互的實現

    Shell腳本之Expect免交互的實現

    Expext概述 Expect是建立在tcl基礎上的一個工具,Expect是用來自動化控制和測試的工具。主要解決shell腳本中不可交互的問題。有助于大規模的系統運維工作。在日常
    2020-01-15
  • Shell腳本實戰之DNS主從同步腳本實例

    Shell腳本實戰之DNS主從同步腳本實例

    DNS主從同步腳本實例 PS:兩個服務器起好后最好兩個服務都重啟一下 主服務器配置 #!/bin/bash #DNS主從同步——主服務器 rpm -q bind if [ $&#63; -ne
    2020-01-15
  • shell之分離解析腳本的實現方法

    shell之分離解析腳本的實現方法

    分離解析腳本 在運行腳本之前,需要VM虛擬機,Centos7,兩臺主機一臺win10 -1 作為廣域網的主機, 一臺win10 -2作為區域網的主機。 之前我的博客有教程 #!/bin/ba
    2020-01-15
  • shell之正向解析腳本的實現方法

    shell之正向解析腳本的實現方法

    正向解析腳本 #!/bin/bash yum install bind -y //安裝解析工具包 //修改主配置文件 sed -i '13s/127.0.0.1/192.168.17.156/' /etc/named.conf //把解析主配
    2020-01-15
  • 淺談用Go構建不可變的數據結構的方法

    淺談用Go構建不可變的數據結構的方法

    共享狀態是比較容易理解和使用的,但是可能產生隱晦以至于很難追蹤的 bugs。尤其是在我們的數據結構只有部分是通過引用傳遞的。切片就是這么一個很好的例子。后續我
    2020-01-15
  • Go 防止 goroutine 泄露的方法

    Go 防止 goroutine 泄露的方法

    概述 Go 的并發模型與其他語言不同,雖說它簡化了并發程序的開發難度,但如果不了解使用方法,常常會遇到 goroutine 泄露的問題。雖然 goroutine 是輕量級的線程,占
    2020-01-15
  • Go實現雙向鏈表的示例代碼

    Go實現雙向鏈表的示例代碼

    本文介紹什么是鏈表,常見的鏈表有哪些,然后介紹鏈表這種數據結構會在哪些地方可以用到,以及 Redis 隊列是底層的實現,通過一個小實例來演示 Redis 隊列有哪些功能
    2020-01-15

最新評論

买宝宝用品赚钱吗