Go Slice vs Maps（翻譯）

原文鏈接
Slices 和 Maps 是 GO 中兩個重要的數(shù)據(jù)類型。這篇博客將記錄我關(guān)于這兩個數(shù)據(jù)結(jié)構(gòu)性能的一些關(guān)鍵發(fā)現(xiàn)劳跃。

在進入性能方面之前，讓我們先簡要看一下 Slices 和 Maps

Slice:
Slices 是建立在數(shù)組之上的一個抽象數(shù)據(jù)結(jié)構(gòu)尊浓。Slice 有一個指向數(shù)組開始的指針过吻，從數(shù)組中可以使用的最大容量以及數(shù)組的長度。Slices 可以根據(jù)需要增長或收縮惕稻。增加一個切片通常涉及到為底層數(shù)組重新分配內(nèi)存竖共。像 copy 和 append 這樣的函數(shù)可以幫助增長數(shù)組

Maps:
GO 中的 Maps 和其他語言(內(nèi)部可能會有所不同)類似。GO中的Map 創(chuàng)建段(每段可以容納8個keys)俺祠。

性能統(tǒng)計:
我對這兩個數(shù)據(jù)結(jié)構(gòu)運行一些基準(zhǔn)測試公给，結(jié)果記錄如下。

樣例總數(shù)	大小	f(n)-[]int(o(N))-循環(huán)并if(lcheck最后一個元素)	map[int]int直接查找o(1)
2百萬	5	5.42ns/op	12.7ns/op
2百萬	10	8.19ns/op	17.8ns/op
2百萬	100	63.3ns/op	16.5ns/op
2百萬	200	118ns/op	16.6ns/op
2百萬	400	228ns/op	18.4ns/op
2百萬	1000	573ns/op	17.0ns/op
2百萬	10000	5674ns/op	17.6ns/op
2百萬	100000	55141ns/op	15.1ns/op

TEST-1:在 slice 中查詢一個INT元素 vs 在map中查找元素 -
這里蜘渣，讓我們試著在長度為n的slice中查找一個條目淌铐，并與在map中查找鍵進行比較。在slice中查找項蔫缸，我們將遍歷該slice并且簡單地使用if來校驗該元素腿准。對于map，我們將簡單地查詢key拾碌。在我們所有的測試中查找最壞的情況吐葱。

樣例總數(shù)	大小	f(n)-[]int(o(N))-循環(huán)并if(lcheck最后一個元素)	map[int]int直接查找o(1)
2百萬	5	5.42ns/op	12.7ns/op
2百萬	10	8.19ns/op	17.8ns/op
2百萬	100	63.3ns/op	16.5ns/op
2百萬	200	118ns/op	16.6ns/op
2百萬	400	228ns/op	18.4ns/op
2百萬	1000	573ns/op	17.0ns/op
2百萬	10000	5674ns/op	17.6ns/op
2百萬	100000	55141ns/op	15.1ns/op

我們可以看到(正如預(yù)期那樣)街望，對于變化的 n 來說，map 查找的復(fù)雜度為常量(O(1))弟跑。然而它匕，有趣的是對于一個小的數(shù)n 一個簡單的for循環(huán)和if判斷，切片花費的時間比map要小窖认，很大的n值將需要更多的時間豫柬。

image

結(jié)論：我推薦使用map來查找給定的key。對于一個很小的大小(n)扑浸，仍然可以使用slice

樣本總數(shù)	長度 – 大小 ( n )	f(n) []string [for loop and if (lcheck for last element)]	f(n) map[string]string
2 百萬	5	30.4 ns/op	32.7 ns/op
2 百萬	10	56.5 ns/op	23.5 ns/op
2 百萬	100	128 ns/op	25.7 ns/op
2 百萬	200	665 ns/op	23.6 ns/op
2 百萬	400	1766 ns/op	23.7 ns/op
2 百萬	1000	905 ns/op	25.7 ns/op
2 百萬	10000	8488 ns/op	24.4 ns/op
2 百萬	100000	82444 ns/op	25.9 ns/op

TEST-2:在一個 slice 中查找一個STRING元素 vs 在 map 中查找一個STRING Key-
我們采取和TEST-1中一樣的步驟烧给，僅僅不同的是這兒我們使用string。

樣本總數(shù)	長度 – 大小 ( n )	f(n) []string [for loop and if (lcheck for last element)]	f(n) map[string]string
2 百萬	5	30.4 ns/op	32.7 ns/op
2 百萬	10	56.5 ns/op	23.5 ns/op
2 百萬	100	128 ns/op	25.7 ns/op
2 百萬	200	665 ns/op	23.6 ns/op
2 百萬	400	1766 ns/op	23.7 ns/op
2 百萬	1000	905 ns/op	25.7 ns/op
2 百萬	10000	8488 ns/op	24.4 ns/op
2 百萬	100000	82444 ns/op	25.9 ns/op

從上面的數(shù)據(jù)喝噪，我們可以看到給定一個key,查找字符串(使用MAP)的復(fù)雜度為O(1)础嫡。對于字符串比較，Maps擊敗了slices

image

結(jié)論：我推薦使用使用maps查找一個給定的字符串類型的key酝惧。即使是更小的'n',使用map也是很好的榴鼎。

樣本總數(shù)	長度 – 大小	[]int (直接索引循環(huán)) – O(1)	[]string (直接索引循環(huán)) – O(1)	map[int]int 直接循環(huán) o(1)	map[string]string o(1)
2 百萬	5	0.30 ns/op	0.29 ns/op	12.7	32.7
2 百萬	10	0.29 ns/op	0.29 ns/op	17.8	23.5
2 百萬	100	0.29 ns/op	0.29 ns/op	16.5	25.7
2 百萬	200	0.29 ns/op	0.29 ns/op	16.6	23.6
2 百萬	400	0.29 ns/op	0.29 ns/op	18.4	23.7
2 百萬	1000	0.29 ns/op	0.29 ns/op	17	25.7
2 百萬	10000	0.58 ns/op	0.57 ns/op	17.6	24.4
2 百萬	100000	0.58 ns/op	0.55 ns/op	15.1	25.9

TEST-3:查找給定索引的一個 slice 元素
如果我們知道索引，然后在GO中查找一個切片晚唇，類似于在任何語言中查找數(shù)組巫财，就像數(shù)組一樣簡單。

樣本總數(shù)	長度 – 大小	[]int (直接索引循環(huán)) – O(1)	[]string (直接索引循環(huán)) – O(1)	map[int]int 直接循環(huán) o(1)	map[string]string o(1)
2 百萬	5	0.30 ns/op	0.29 ns/op	12.7	32.7
2 百萬	10	0.29 ns/op	0.29 ns/op	17.8	23.5
2 百萬	100	0.29 ns/op	0.29 ns/op	16.5	25.7
2 百萬	200	0.29 ns/op	0.29 ns/op	16.6	23.6
2 百萬	400	0.29 ns/op	0.29 ns/op	18.4	23.7
2 百萬	1000	0.29 ns/op	0.29 ns/op	17	25.7
2 百萬	10000	0.58 ns/op	0.57 ns/op	17.6	24.4
2 百萬	100000	0.58 ns/op	0.55 ns/op	15.1	25.9

如上圖所示哩陕，直接查找切片是O(1)恒定的生長速率平项。

image

結(jié)論：直接查找是的復(fù)雜度是常量，因此悍及，如果您知道索引闽瓢，那么i使用哪一個就不重要了。然而心赶，索引是已知的話扣讼，slice/array查找仍然是比map查找要快

樣本總數(shù)	長度 – 大小 ( n )	遍歷整型 slice O(N)	遍歷整型 Map O(N)
2 百萬	5	9.02 ns/op	107 ns/op
2 百萬	10	12.5 ns/op	196 ns/op
2 百萬	100	59.2 ns/op	1717 ns/o
2 百萬	200	84.9 ns/op	3356 ns/op
2 百萬	400	155 ns/op	6677 ns/op
2 百萬	1000	315 ns/op	18906 ns/op
2 百萬	10000	2881 ns/op	178804 ns/op***
2 百萬	100000	29012 ns/op	1802439 ns/op***

TEST-4:遍歷一個Slice vs 遍歷一個Map
這里我嘗試遍歷一個map和slice，并且在這個循環(huán)中執(zhí)行一個恒定的操作缨叫。整體的復(fù)雜度將仍然是O(N)椭符。

樣本總數(shù)	長度 – 大小 ( n )	遍歷整型 slice O(N)	遍歷整型 Map O(N)
2 百萬	5	9.02 ns/op	107 ns/op
2 百萬	10	12.5 ns/op	196 ns/op
2 百萬	100	59.2 ns/op	1717 ns/o
2 百萬	200	84.9 ns/op	3356 ns/op
2 百萬	400	155 ns/op	6677 ns/op
2 百萬	1000	315 ns/op	18906 ns/op
2 百萬	10000	2881 ns/op	178804 ns/op***
2 百萬	100000	29012 ns/op	1802439 ns/op***

正如我們在上面看到的。遍歷一個slice比遍歷一個map快將近20倍弯汰。這個原因是slice(基于數(shù)組的抽象)被創(chuàng)建是在一個連續(xù)的內(nèi)在塊上艰山，不像maps。在maps的例子中咏闪，循環(huán)不得不迭代鍵空間(在GO中稱為桶)并且內(nèi)存塊被分配不是連續(xù)的。這就是為什么每次運行時摔吏，遍歷映射的結(jié)果會以不同的順序顯示鍵/值鸽嫂。

image

系統(tǒng)詳情	goos:darwin	Go-1.9.2
MAC-OSX	goarch:amd64

結(jié)論：如果要求是打印或執(zhí)行一個操作而不是查找整個列表元素纵装，slice是最好的選擇。上面描述的原因据某，遍歷Maps花費更多的時候
另外橡娄，請注意，在slice上的append操作保證了O(1)癣籽，就像插入到map挽唉，但這是一個平攤的常數(shù)。Append可能偶爾需要重新分配底層數(shù)組的內(nèi)存
(***)-樣例大小減少到2000而不是200萬作為Go的大型Maps基準(zhǔn)測試函數(shù)
關(guān)于測試的詳情:

系統(tǒng)詳情	goos:darwin	Go-1.9.2
MAC-OSX	goarch:amd64

源代碼：

//m-c02jn0m1f1g4:slicevsmap user1$ cat slicemap.go 

package slicemap
//You can uncomment print to see the results(to confirm if code is working). 
//But for benchmark, we don't care about printing results.We are concerned about time it takes to run

//import "fmt"

func RangeSliceInt(input []int, find int) (index int) {
    for index,value := range input {
        if (value == find) {
      // fmt.Println("found at",index)
            return index
        }
    }

    return -1
}


func RangeSliceIntPrint(input []int) {
    for _,_ = range input {
        continue
    }
}

func MapLookupInt(input map[int]int, find int) (key,value int) {
    if value,ok := input[find];ok {
    // fmt.Println("found at", find,value)
        return find,value
    }
    return 0,0
}

func MapRangeInt(input map[int]int) {
    for _,_ = range input {
        continue
    }
}

func DirectSliceInt(input []int, index int) int {
    return input[index]
}

// FOR STRINGS //
func RangeSliceString(input []string, find string) (index int) {
  for index,value := range input {
    if (value == find) {
      //fmt.Println("found at",index)
      return index
    }
  }
  return -1
}

func RangeSliceStringPrint(input []string) {
  for _,_ = range input {
    continue
  }
}

func MapLookupString(input map[string]string, find string) (key,value string) {
  if value,ok := input[find];ok {
    // fmt.Println("found at", find,value)
    return find,value
  }
  return "0","0"
}

func MapRangeString(input map[string]string) {
  for _,_ = range input {
    continue
  }
}

func DirectSliceString(input []string, index int) string {
  return input[index]
}

//m-c02jn0m1f1g4:slicevsmap user1$ cat slicemap_test.go
package slicemap

import (
  "testing"
  "strconv"
)

func Benchmark_TimeRangeSliceInt(b *testing.B) {

  b.StopTimer()

    input := make([]int, 100000, 500000)

    for i := 0; i < 100000; i++ {
        input[i] = i+10
    }

    b.StartTimer()

    b.N = 2000000  //just to avoid 百萬s of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)

    for i := 0; i < b.N; i++ {
        RangeSliceInt(input, 100009)  //check for the last item for worst case
    }
}


func Benchmark_TimeDirectSliceInt(b *testing.B) {

    b.StopTimer()

  input := make([]int, 100000, 500000)

  for i := 0; i < 100000; i++ {
    input[i] = i+10
  }

  b.StartTimer()        

  b.N = 2000000  //just to avoid 百萬s of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)    

  for i := 0; i < b.N; i++ {
     DirectSliceInt(input, 99999)  //directly check for value given a index. o(1). sending the index
  }
}

func Benchmark_TimeMapLookupInt(b *testing.B) {

    b.StopTimer()

    input := make(map[int]int)

    //throw in some values into the map

    for i := 1; i <=100000; i++ {

        input[i] = i+10

    }

    b.StartTimer()

    b.N = 2000000  //just to avoid 百萬s of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)

    for k := 0; k < b.N; k++ { 

        MapLookupInt(input, 100000)

    }

/*

to run this 

go test -bench=Benchmark_TimeMapLookup

*/

}


func Benchmark_TimeSliceRangeInt(b *testing.B) {

    b.StopTimer()

  input := make([]int, 5, 10)

  for i := 0; i < 5; i++ {
    input[i] = i+10
  }

  b.StartTimer()

  b.N = 2000000  //just to avoid 百萬s of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)

  for k := 0; k < b.N; k++ {
    RangeSliceIntPrint(input)
  }

}

func Benchmark_TimeMapRangeInt(b *testing.B) {

  b.StopTimer()

  input := make(map[int]int)

  //throw in some values into the map

  for i := 1; i <=100000; i++ {
    input[i] = i+10
  }

  b.StartTimer()

  b.N = 2000  //just to avoid 百萬s of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)

  for k := 0; k < b.N; k++ {
    MapRangeInt(input)
  }

}


// Tests for String

func Benchmark_TimeRangeSliceString(b *testing.B) {

  b.StopTimer()

  input := make([]string, 100000, 500000)

  for i := 0; i < 100000; i++ {
    input[i] = strconv.FormatInt(int64(i+10),10)
  }

  b.StartTimer()

  b.N = 2000000  //just to avoid 百萬s of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)

  for i := 0; i < b.N; i++ {
    RangeSliceString(input, "100009")  //check for the last item for worst case
  }

}


func Benchmark_TimeDirectSliceString(b *testing.B) {
  b.StopTimer()
  input := make([]string, 100000, 500000)

  for i := 0; i < 100000; i++ {
    input[i] = strconv.FormatInt(int64(i+10),10)
  }

  b.StartTimer()

  b.N = 2000000  //just to avoid 百萬s of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)
  for i := 0; i < b.N; i++ {
    DirectSliceString(input, 99999)  //directly check for value given a index. o(1)
  }
}


func Benchmark_TimeMapLookupString(b *testing.B) {
  b.StopTimer()
  input := make(map[string]string)

  //throw in some values into the map

  for i := 1; i <=100000; i++ {
    input[strconv.FormatInt(int64(i),10)] = strconv.FormatInt(int64(i+10),10)
  }

  b.StartTimer()

  b.N = 2000000  //just to avoid 百萬s of fmt.Println (in case you are doing fmt.Println in the slicemap.go package)

  for k := 0; k < b.N; k++ {
    MapLookupString(input, "100000")
  }

/*
to run this
go test -bench=Benchmark_TimeMapLookupString
*/

}

最后編輯于：2017.11.22 15:00:25

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末筷狼，一起剝皮案震驚了整個濱河市瓶籽，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌埂材，老刑警劉巖塑顺，帶你破解...
沈念sama閱讀 206,482評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異俏险，居然都是意外死亡严拒，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,377評論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門竖独，熙熙樓的掌柜王于貴愁眉苦臉地迎上來裤唠，“玉大人，你說我怎么就攤上這事莹痢∏缮В” “怎么了？”我有些...
開封第一講書人閱讀 152,762評論 0贊 342
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵格二，是天一觀的道長劈彪。經(jīng)常有香客問我，道長顶猜，這世上最難降的妖魔是什么沧奴？我笑而不...
開封第一講書人閱讀 55,273評論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮长窄，結(jié)果婚禮上滔吠，老公的妹妹穿的比我還像新娘。我一直安慰自己挠日，他們只是感情好疮绷，可當(dāng)我...
茶點故事閱讀 64,289評論 5贊 373
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著嚣潜，像睡著了一般冬骚。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,046評論 1贊 285
城市分裂傳說
那天只冻，我揣著相機與錄音庇麦，去河邊找鬼。笑死喜德，一個胖子當(dāng)著我的面吹牛山橄，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播舍悯，決...
沈念sama閱讀 38,351評論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼航棱，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了萌衬？” 一聲冷哼從身側(cè)響起饮醇，我...
開封第一講書人閱讀 36,988評論 0贊 259
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎奄薇，沒想到半個月后驳阎，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 43,476評論 1贊 300
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡馁蒂，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 35,948評論 2贊 324
?白月光啟示錄
正文我和宋清朗相戀三年呵晚，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片沫屡。...
茶點故事閱讀 38,064評論 1贊 333
活死人
序言：一個原本活蹦亂跳的男人離奇死亡饵隙，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出沮脖，到底是詐尸還是另有隱情金矛，我是刑警寧澤，帶...
沈念sama閱讀 33,712評論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布勺届，位于F島的核電站驶俊，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏免姿。R本人自食惡果不足惜饼酿，卻給世界環(huán)境...
茶點故事閱讀 39,261評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望胚膊。院中可真熱鬧故俐，春花似錦、人聲如沸紊婉。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,264評論 0贊 19
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽喻犁。三九已至槽片，卻和暖如春何缓，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背筐乳。一陣腳步聲響...
開封第一講書人閱讀 31,486評論 1贊 262
情欲美人皮
我被黑心中介騙來泰國打工歌殃，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留乔妈，地道東北人蝙云。一個月前我還...
沈念sama閱讀 45,511評論 2贊 354
代替公主和親
正文我出身青樓，卻偏偏與公主長得像路召，于是被迫代替她去往敵國和親勃刨。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 42,802評論 2贊 345

Go Slice vs Maps（翻譯）

推薦閱讀更多精彩內(nèi)容