Go 中 slice 的 In 功能實現探索

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

之前在知乎看到一個問題:為什么 Golang 沒有像 Python 中 in 一樣的功能?于是,搜了下這個問題,發現還是有不少人有這樣的疑問。
今天來談談這個話題。
in 是一個

之前在知乎看到一個問題:為什么 Golang 沒有像 Python 中 in 一樣的功能?于是,搜了下這個問題,發現還是有不少人有這樣的疑問。

今天來談談這個話題。

in 是一個很常用的功能,有些語言中可能也稱為 contains,雖然不同語言的表示不同,但基本都是有的。不過可惜的是,Go 卻沒有,它即沒有提供類似 Python 操作符 in,也沒有像其他語言那樣提供這樣的標準庫函數,如 PHP 中 in_array。

Go 的哲學是追求少即是多。我想或許 Go 團隊覺得這是一個實現起來不足為道的功能吧。

為何說微不足道?如果要自己實現,又該如何做呢?

我所想到的有三種實現方式,一是遍歷,二是 sort 的二分查找,三是 map 的 key 索引。

本文相關源碼已經上傳在我的 github 上, poloxue/gotin 。

遍歷

遍歷應該是我們最容易想到的最簡單的實現方式。

示例如下:

func InIntSlice(haystack []int, needle int) bool {
 for _, e := range haystack {
 if e == needle {
 return true
 }
 }

 return false
}

上面演示了如何在一個 []int 類型變量中查找指定 int 是否存在的例子,是不是非常簡單,由此我們也可以感受到我為什么說它實現起來微不足道。

這個例子有個缺陷,它只支持單一類型。如果要支持像解釋語言一樣的通用 in 功能,則需借助反射實現。

代碼如下:

func In(haystack interface{}, needle interface{}) (bool, error) {
 sVal := reflect.ValueOf(haystack)
 kind := sVal.Kind()
 if kind == reflect.Slice || kind == reflect.Array {
 for i := 0; i < sVal.Len(); i++ {
 if sVal.Index(i).Interface() == needle {
 return true, nil
 }
 }

 return false, nil
 }

 return false, ErrUnSupportHaystack
}

為了更加通用,In 函數的輸入參數 haystack 和 needle 都是 interface{} 類型。

簡單說說輸入參數都是 interface{} 的好處吧,主要有兩點,如下:

其一,haystack 是 interface{} 類型,使 in 支持的類型不止于 slice,還包括 array。我們看到,函數內部通過反射對 haystack 進行了類型檢查,支持 slice(切片)與 array(數組)。如果是其他類型則會提示錯誤,增加新的類型支持,如 map,其實也很簡單。但不推薦這種方式,因為通過 _, ok := m[k] 的語法即可達到 in 的效果。

其二,haystack 是 interface{},則 []interface{} 也滿足要求,并且 needle 是 interface{}。如此一來,我們就可以實現類似解釋型語言一樣的效果了。

怎么理解?直接示例說明,如下:

gotin.In([]interface{}{1, "two", 3}, "two")

haystack 是 []interface{}{1, "two", 3},而且 needle 是 interface{},此時的值是 "two"。如此看起來,是不是實現了解釋型語言中,元素可以是任意類型,不必完全相同效果。如此一來,我們就可以肆意妄為的使用了。

但有一點要說明,In 函數的實現中有這樣一段代碼:

if sVal.Index(i).Interface() == needle {
 ...
}

Go 中并非任何類型都可以使用 == 比較的,如果元素中含有 slice 或 map,則可能會報錯。

二分查找

以遍歷確認元素是否存在有個缺點,那就是,如果數組或切片中包含了大量數據,比如 1000000 條數據,即一百萬,最壞的情況是,我們要遍歷 1000000 次才能確認,時間復雜度 On。

有什么辦法可以降低遍歷次數?

自然而然地想到的方法是二分查找,它的時間復雜度 log2(n) 。但這個算法有前提,需要依賴有序序列。

于是,第一個要我們解決的問題是使序列有序,Go 的標準庫已經提供了這個功能,在 sort 包下。

示例代碼如下:

fmt.Println(sort.SortInts([]int{4, 2, 5, 1, 6}))

對于 []int,我們使用的函數是 SortInts,如果是其他類型切片,sort 也提供了相關的函數,比如 []string 可通過 SortStrings 排序。

完成排序就可以進行二分查找,幸運的是,這個功能 Go 也提供了,[]int 類型對應函數是 SearchInts。

簡單介紹下這個函數,先看定義:

func SearchInts(a []int, x int) int

輸入參數容易理解,從切片 a 中搜索 x。重點要說下返回值,這對于我們后面確認元素是否存在至關重要。返回值的含義,返回查找元素在切片中的位置,如果元素不存在,則返回,在保持切片有序情況下,插入該元素應該在什么位置。

比如,序列如下:

1 2 6 8 9 11

假設,x 為 6,查找之后將發現它的位置在索引 2 處;x 如果是 7,發現不存在該元素,如果插入序列,將會放在 6 和 8 之間,索引位置是 3,因而返回值為 3。

代碼測試下:

fmt.Println(sort.SearchInts([]int{1, 2, 6, 8, 9, 11}, 6)) // 2
fmt.Println(sort.SearchInts([]int{1, 2, 6, 8, 9, 11}, 7)) // 3

如果判斷元素是否在序列中,只要判斷返回位置上的值是否和查找的值相同即可。

但還有另外一種情況,如果插入元素位于序列最后,例如元素值為 12,插入位置即為序列的長度 6。如果直接查找 6 位置上的元素就可能發生越界的情況。那怎么辦呢?其實判斷返回是否大于切片長度即可,大于則說明元素不在切片序列中。

完整的實現代碼如下:

func SortInIntSlice(haystack []int, needle int) bool {
 sort.Ints(haystack)

 index := sort.SearchInts(haystack, needle)
 return index < len(haystack) && haystack[index] == needle
}

但這還有個問題,對于無序的場景,如果每次查詢都要經過一次排序并不劃算。最后能實現一次排序,稍微修改下代碼。

func InIntSliceSortedFunc(haystack []int) func(int) bool {
 sort.Ints(haystack)

 return func(needle int) bool {
 index := sort.SearchInts(haystack, needle)
 return index < len(haystack) && haystack[index] == needle
 }
}

上面的實現,我們通過調用 InIntSliceSortedFunc 對 haystack 切片排序,并返回一個可多次使用的函數。

使用案例如下:

in := gotin.InIntSliceSortedFunc(haystack)

for i := 0; i<maxNeedle; i++ {
 if in(i) {
 fmt.Printf("%d is in %v", i, haystack)
 }
}

二分查找的方式有什么不足呢?

我想到的重要一點,要實現二分查找,元素必須是可排序的,如 int,string,float 類型。而對于結構體、切片、數組、映射等類型,使用起來就不是那么方便,當然,如果要用,也是可以的,不過需要我們進行一些適當擴展,按指定標準排序,比如結構的某個成員。

到此,二分查找的 in 實現就介紹完畢了。

map key

本節介紹 map key 方式。它的算法復雜度是 O1,無論數據量多大,查詢性能始終不變。它主要依賴的是 Go 中的 map 數據類型,通過 hash map 直接檢查 key 是否存在,算法大家應該都比較熟悉,通過 key 可直接映射到索引位置。

我們常會用到這個方法。

_, ok := m[k]
if ok {
 fmt.Println("Found")
}

那么它和 in 如何結合呢?一個案例就說明白了這個問題。

假設,我們有一個 []int 類型變量,如下:

s := []int{1, 2, 3}

為了使用 map 的能力檢查某個元素是否存在,可以將 s 轉化 map[int]struct{}。

m := map[interface{}]struct{}{
 1: struct{}{},
 2: struct{}{},
 3: struct{}{},
 4: struct{}{},
}

如果檢查某個元素是否存在,只需要通過如下寫法即可確定:

k := 4
if _, ok := m[k]; ok {
 fmt.Printf("%d is found\n", k)
}

是不是非常簡單?

補充一點,關于這里為什么使用 struct{},可以閱讀我之前寫的一篇關于Go 中如何使用 set 的文章。

按照這個思路,實現函數如下:

func MapKeyInIntSlice(haystack []int, needle int) bool {
 set := make(map[int]struct{})

 for _ , e := range haystack {
 set[e] = struct{}{}
 }

 _, ok := set[needle]
 return ok
}

實現起來不難,但和二分查找有著同樣的問題,開始要做數據處理,將 slice 轉化為 map。如果是每次數據相同,稍微修改下它的實現。

func InIntSliceMapKeyFunc(haystack []int) func(int) bool {
 set := make(map[int]struct{})

 for _ , e := range haystack {
 set[e] = struct{}{}
 }

 return func(needle int) bool {
 _, ok := set[needle]
 return ok
 }
}

對于相同的數據,它會返回一個可多次使用的 in 函數,一個使用案例如下:

in := gotin.InIntSliceMapKeyFunc(haystack)

for i := 0; i<maxNeedle; i++ {
 if in(i) {
 fmt.Printf("%d is in %v", i, haystack)
 }
}

對比前兩種算法,這種方式的處理效率最高,非常適合于大數據的處理。接下來的性能測試,我們將會看到效果。

性能

介紹完所有方式,我們來實際對比下每種算法的性能。測試源碼位于gotin_test.go 文件中。

基準測試主要是從數據量大小考察不同算法的性能,本文中選擇了三個量級的測試樣本數據,分別是 10、1000、1000000。

為便于測試,首先定義了一個用于生成 haystack 和 needle 樣本數據的函數。

代碼如下:

func randomHaystackAndNeedle(size int) ([]int, int){
 haystack := make([]int, size)

 for i := 0; i<size ; i++{
 haystack[i] = rand.Int()
 }

 return haystack, rand.Int()
}

輸入參數是 size,通過 rand.Int() 隨機生成切片大小為 size 的 haystack 和 1 個 needle。在基準測試用例中,引入這個隨機函數生成數據即可。

舉個例子,如下:

func BenchmarkIn_10(b *testing.B) {
 haystack, needle := randomHaystackAndNeedle(10)

 b.ResetTimer()
 for i := 0; i < b.N; i++ {
 _, _ = gotin.In(haystack, needle)
 }
}

首先,通過 randomHaystackAndNeedle 隨機生成了一個含有 10 個元素的切片。因為生成樣本數據的時間不應該計入到基準測試中,我們使用 b.ResetTimer() 重置了時間。

其次,壓測函數是按照 Test+函數名+樣本數據量 規則編寫,如案例中 BenchmarkIn_10,表示測試 In 函數,樣本數據量為 10。如果我們要用 1000 數據量測試 InIntSlice,壓測函數名為 BenchmarkInIntSlice_1000。

測試開始吧!簡單說下我的筆記本配置,Mac Pro 15 版,16G 內存,512 SSD,4 核 8 線程的 CPU。

測試所有函數在數據量在 10 的情況下的表現。

$ go test -run=none -bench=10$ -benchmem

匹配所有以 10 結尾的壓測函數。

測試結果:

goos: darwin
goarch: amd64
pkg: github.com/poloxue/gotin
BenchmarkIn_10-8 3000000 501 ns/op 112 B/op 11 allocs/op
BenchmarkInIntSlice_10-8 200000000 7.47 ns/op 0 B/op 0 allocs/op
BenchmarkInIntSliceSortedFunc_10-8 100000000 22.3 ns/op 0 B/op 0 allocs/op
BenchmarkSortInIntSlice_10-8 10000000 162 ns/op 32 B/op 1 allocs/op
BenchmarkInIntSliceMapKeyFunc_10-8 100000000 17.7 ns/op 0 B/op 0 allocs/op
BenchmarkMapKeyInIntSlice_10-8 3000000 513 ns/op 163 B/op 1 allocs/op
PASS
ok github.com/poloxue/gotin 13.162s

表現最好的并非 SortedFunc 和 MapKeyFunc,而是最簡單的針對單類型的遍歷查詢,平均耗時 7.47ns/op,當然,另外兩種方式表現也不錯,分別是 22.3ns/op 和 17.7ns/op。

表現最差的是 In、SortIn(每次重復排序) 和 MapKeyIn(每次重復創建 map)兩種方式,平均耗時分別為 501ns/op 和 513ns/op。

測試所有函數在數據量在 1000 的情況下的表現。

$ go test -run=none -bench=1000$ -benchmem

測試結果:

goos: darwin
goarch: amd64
pkg: github.com/poloxue/gotin
BenchmarkIn_1000-8 30000 45074 ns/op 8032 B/op 1001 allocs/op
BenchmarkInIntSlice_1000-8 5000000 313 ns/op 0 B/op 0 allocs/op
BenchmarkInIntSliceSortedFunc_1000-8 30000000 44.0 ns/op 0 B/op 0 allocs/op
BenchmarkSortInIntSlice_1000-8 20000 65401 ns/op 32 B/op 1 allocs/op
BenchmarkInIntSliceMapKeyFunc_1000-8 100000000 17.6 ns/op 0 B/op 0 allocs/op
BenchmarkMapKeyInIntSlice_1000-8 20000 82761 ns/op 47798 B/op 65 allocs/op
PASS
ok github.com/poloxue/gotin 11.312s

表現前三依然是 InIntSlice、InIntSliceSortedFunc 和 InIntSliceMapKeyFunc,但這次順序發生了變化,MapKeyFunc 表現最好,17.6 ns/op,與數據量 10 的時候相比基本無變化。再次驗證了前文的說法。

同樣的,數據量 1000000 的時候。

$ go test -run=none -bench=1000000$ -benchmem

測試結果如下:

goos: darwin
goarch: amd64
pkg: github.com/poloxue/gotin
BenchmarkIn_1000000-8 30 46099678 ns/op 8000098 B/op 1000001 allocs/op
BenchmarkInIntSlice_1000000-8 3000 424623 ns/op 0 B/op 0 allocs/op
BenchmarkInIntSliceSortedFunc_1000000-8 20000000 72.8 ns/op 0 B/op 0 allocs/op
BenchmarkSortInIntSlice_1000000-8 10 138873420 ns/op 32 B/op 1 allocs/op
BenchmarkInIntSliceMapKeyFunc_1000000-8 100000000 16.5 ns/op 0 B/op 0 allocs/op
BenchmarkMapKeyInIntSlice_1000000-8 10 156215889 ns/op 49824225 B/op 38313 allocs/op
PASS
ok github.com/poloxue/gotin 15.178s

MapKeyFunc 依然表現最好,每次操作用時 17.2 ns,Sort 次之,而 InIntSlice 呈現線性增加的趨勢。一般情況下,如果不是對性能要特殊要求,數據量特別大的場景,針對單類型的遍歷已經有非常好的性能了。

從測試結果可以看出,反射實現的通用 In 函數每次執行需要進行大量的內存分配,方便的同時,也是以犧牲性能為代價的。

總結

本文通過一個問題引出主題,為什么 Go 中沒有類似 Python 的 In 方法。我認為,一方面是實現非常簡單,沒有必要。除此以外,另一方面,在不同場景下,我們還需要根據實際情況分析用哪種方式實現,而不是一種固定的方式。

接著,我們介紹了 In 實現的三種方式,并分析了各自的優劣。通過性能分析測試,我們能得出大致的結論,什么方式適合什么場景,但總體還是不能說足夠細致,有興趣的朋友可以繼續研究下。

您可能感興趣的文章:

  • Golang 探索對Goroutine的控制方法(詳解)

相關文章

  • Go 中 slice 的 In 功能實現探索

    Go 中 slice 的 In 功能實現探索

    之前在知乎看到一個問題:為什么 Golang 沒有像 Python 中 in 一樣的功能?于是,搜了下這個問題,發現還是有不少人有這樣的疑問。 今天來談談這個話題。 in 是一個
    2020-01-15
  • 詳解Go中Set的實現方式

    詳解Go中Set的實現方式

    本篇主要講述如何利用Go語言的語法特性實現Set類型的數據結構。 需求 對于Set類型的數據結構,其實本質上跟List沒什么多大的區別。無非是Set不能含有重復的Item的
    2020-01-15
  • 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

最新評論

老快3投注技巧 百度江西多乐彩开奖 决定股票涨跌的因素 上海时时乐今天的开奖号码 江西多乐彩11选5开奖公告 山东十一选五一定牛走势图 幸运快3大小单双 股票推荐群推荐比特币 云南快乐10分前三推算 年股票指数 安徽11选五综合走势图 重庆时时全天计划qq群 11选5云南 大发快三计划软件 福利彩票东方6十1开奖号码 山西快乐十分奖金规则 内部三肖期期中