golang中拿slice當(dāng)queue和拿list當(dāng)queue使用分析
前言
我記得曾經(jīng)有一次參加面試時(shí)，在答題過(guò)程中非常嘴欠地說(shuō)了一句：“我之所以代碼這么寫，因?yàn)樵?golang 中沒(méi)有內(nèi)置的無(wú)限長(zhǎng)度 queue 的實(shí)現(xiàn)……”，當(dāng)時(shí)說(shuō)完我就后悔了，面試我的人，前幾個(gè)問(wèn)題本就有那么幾分刻薄，一聽(tīng)這一句，立馬就來(lái)勁了：“誰(shuí)說(shuō)沒(méi)有？誰(shuí)說(shuō)沒(méi)有？”
好在我連連改口，巧舌如簧，搪塞了過(guò)去。我明白，在大牛們的手里，只需最簡(jiǎn)單的數(shù)組，稍微加幾個(gè)“簡(jiǎn)單的”函數(shù)，搖身一變，就可以成為“現(xiàn)成的”隊(duì)列、棧、環(huán)、二叉樹(shù)、圖……
我不僅不是大牛，我還是個(gè)懶漢，我希望的內(nèi)置的隊(duì)列，是拿過(guò)來(lái)就能 dequeue、enqueue 的工具，但 golang 的標(biāo)準(zhǔn)庫(kù)里并沒(méi)有名字叫 queue 的內(nèi)置對(duì)象，只用 channel 可以在某些時(shí)候當(dāng)隊(duì)列來(lái)用，但是一個(gè) channel 是有長(zhǎng)度限制的，超過(guò) channel 的長(zhǎng)度了還繼續(xù)入隊(duì)會(huì)觸發(fā)阻塞，舉個(gè)例子：二叉樹(shù)的逐層遍歷，第一想到的是用隊(duì)列去做吧？但你不知道二叉樹(shù)的尺寸，你敢用 channel 懟上去嗎？
網(wǎng)上有很對(duì)文章展示了如何自己實(shí)現(xiàn)一個(gè)隊(duì)列，看起來(lái)似乎也沒(méi)啥問(wèn)題，但我說(shuō)了我很懶，我不想自己手寫一個(gè)隊(duì)列。你說(shuō)可以把網(wǎng)上的代碼復(fù)制粘貼過(guò)來(lái)？那我們猜個(gè)謎，問(wèn)：什么實(shí)現(xiàn)最有可能需要實(shí)現(xiàn)逐層遍歷二叉樹(shù)？
答案是：面試的時(shí)候。那你是要我面試的時(shí)候把把網(wǎng)上的代碼復(fù)制粘貼過(guò)來(lái)嗎？
……
雖然 golang 沒(méi)有內(nèi)置的 queue，但它還是提供了很多強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，那有沒(méi)有可以直接拿過(guò)來(lái)當(dāng) queue 來(lái)使的呢？有的，且至少有兩個(gè)選項(xiàng)。強(qiáng)調(diào)一句，我們這里并不討論線程安全隊(duì)列，僅是普通的無(wú)容量限制隊(duì)列。
拿 slice 當(dāng) queue
我敢打賭，slice 是你在 golang 中用到的最頻繁的數(shù)據(jù)結(jié)構(gòu)了，它基于底層數(shù)組實(shí)現(xiàn)的，但又比數(shù)組要強(qiáng)大的多。拿來(lái)當(dāng)隊(duì)列用，slice 是完全能勝任的。
初始化一個(gè)隊(duì)里：
var queue []int
入隊(duì)一個(gè)元素：
queue = append(queue, 1)
出隊(duì)一個(gè)元素：
if len(queue) > 1 {
queue = queue[1:]
}看吧，簡(jiǎn)單明了，易學(xué)易用。
但你會(huì)不會(huì)有一點(diǎn)覺(jué)得 queue = queue[1:] 這樣的寫法有一點(diǎn)挫？白白浪費(fèi)掉了 slice 前端元素的內(nèi)存，和隊(duì)列的假溢出問(wèn)題有點(diǎn)像，當(dāng)然 slice 會(huì)自動(dòng)擴(kuò)容，并不會(huì)發(fā)生假溢出，且每次擴(kuò)容時(shí)會(huì)重新開(kāi)辟新數(shù)組，拷貝元素到新數(shù)組時(shí)并不會(huì)拷貝被棄用的元素，所以內(nèi)存的浪費(fèi)還是在可控的范圍內(nèi)的。我們可以跑一個(gè)例子加以說(shuō)明：
// 一個(gè)空的 cap 為 5 的 slice
queue := make([]int, 0, 5) // _ _ _ _ _
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 輸出 len(queue): 0, cap(queue): 5, queue: []
// 入隊(duì)一個(gè)元素
queue = append(queue, 1) // [1] _ _ _ _
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 輸出 len(queue): 1, cap(queue): 5, queue: [1]
// 再入隊(duì)一個(gè)元素
queue = append(queue, 2) // [1 2] _ _ _
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 輸出 len(queue): 2, cap(queue): 5, queue: [1 2]
// 出隊(duì)一個(gè)元素
queue = queue[1:] // 1 [2] _ _ _
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 輸出 len(queue): 1, cap(queue): 4, queue: [2]
// 再入隊(duì)三個(gè)元素
queue = append(queue, 3, 4, 5) // 1 [2 3 4 5]
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 輸出 len(queue): 4, cap(queue): 4, queue: [2 3 4 5]
// 出隊(duì)二個(gè)元素
queue = queue[2:] // 1 2 3 [4 5]
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 輸出 len(queue): 2, cap(queue): 2, queue: [4 5]
// 再入隊(duì)一個(gè)元素，觸發(fā) slise 的擴(kuò)容，根據(jù)擴(kuò)容策略，此時(shí) slice cap 為 2，翻倍為 4
queue = append(queue, 6) // // [4 5 6] _
fmt.Printf("len(queue): %v, cap(queue): %v, queue: %v\n", len(queue), cap(queue), queue)
// 輸出 len(queue): 3, cap(queue): 4, queue: [4 5 6]不過(guò)你可以看到了，當(dāng)不斷地入隊(duì)出隊(duì)，slice 的需要反復(fù)擴(kuò)容，這也可能造成一定的 CPU 消耗。且 queue = queue[1:] 這樣的寫法未免也太簡(jiǎn)單粗暴了一點(diǎn)，有沒(méi)有更高大上的做法呢，我們且看另一種可以拿來(lái)當(dāng)隊(duì)列用的數(shù)據(jù)結(jié)構(gòu)。
拿 list 當(dāng) queue
這里的 list 指的是 golang 內(nèi)置的包 container/list，是這是一個(gè)雙向鏈表的實(shí)現(xiàn)，如果你不了解它，可以花幾分鐘看一下這篇 《container — 容器數(shù)據(jù)類型：heap、list和ring》，這里復(fù)制粘貼一下，把 list 對(duì)應(yīng)的方法列舉一下：
type Element
func (e *Element) Next() *Element
func (e *Element) Prev() *Element
type List
func New() *List
func (l *List) Back() *Element // 最后一個(gè)元素
func (l *List) Front() *Element // 第一個(gè)元素
func (l *List) Init() *List // 鏈表初始化
func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在某個(gè)元素后插入
func (l *List) InsertBefore(v interface{}, mark *Element) *Element // 在某個(gè)元素前插入
func (l *List) Len() int // 在鏈表長(zhǎng)度
func (l *List) MoveAfter(e, mark *Element) // 把e元素移動(dòng)到mark之后
func (l *List) MoveBefore(e, mark *Element) // 把e元素移動(dòng)到mark之前
func (l *List) MoveToBack(e *Element) // 把e元素移動(dòng)到隊(duì)列最后
func (l *List) MoveToFront(e *Element) // 把e元素移動(dòng)到隊(duì)列最頭部
func (l *List) PushBack(v interface{}) *Element // 在隊(duì)列最后插入元素
func (l *List) PushBackList(other *List) // 在隊(duì)列最后插入接上新隊(duì)列
func (l *List) PushFront(v interface{}) *Element // 在隊(duì)列頭部插入元素
func (l *List) PushFrontList(other *List) // 在隊(duì)列頭部插入接上新隊(duì)列
func (l *List) Remove(e *Element) interface{} // 刪除某個(gè)元素
當(dāng)然我們是不用關(guān)心這么多方法的，拿來(lái)當(dāng)隊(duì)列用的話，還是很簡(jiǎn)單的：
初始化一個(gè)隊(duì)里：
queue := list.New()
入隊(duì)一個(gè)元素：
queue.PushBack(1)
出隊(duì)一個(gè)元素：
if queue.Len() > 1 {
queue.Remove(queue.Front())
}queue.Remove(queue.Front()) 比 queue = queue[1:] 看起來(lái)高大上多了有沒(méi)有？由于是基于鏈表的，自然也沒(méi)有內(nèi)存浪費(fèi)或假溢出的情況，你是不是已經(jīng)決定好了，以后要用隊(duì)列就用它了。
由于不需要像 slice 那樣在擴(kuò)容時(shí)大量拷貝元素，list 作為隊(duì)列一定比 slice 性能好得多，難道不是嗎？
性能對(duì)比
且慢，口說(shuō)無(wú)憑，我們做個(gè)性能測(cè)試吧。
測(cè)試代碼我已經(jīng)寫好了，測(cè)試邏輯是這樣的，每次往隊(duì)列里入隊(duì)兩個(gè)元素，再出隊(duì)一個(gè)元素，保持隊(duì)列的中元素?cái)?shù)量持續(xù)增長(zhǎng)。且看代碼：
import (
"container/list"
"testing"
)
func BenchmarkListQueue(b *testing.B) {
q := list.New()
for i := 0; i < b.N; i++ {
q.PushBack(1)
q.PushBack(1)
q.Remove(q.Front())
}
}
func BenchmarkSliceQueue(b *testing.B) {
var q []int
for i := 0; i < b.N; i++ {
q = append(q, 1)
q = append(q, 1)
q = q[1:]
}
}運(yùn)行結(jié)果：
$ go test -bench=. -benchmem -count=3
goos: darwin
goarch: amd64
pkg: tinylib/queue/queue_test
BenchmarkListQueue-12 10000000 144 ns/op 96 B/op 2 allocs/op
BenchmarkListQueue-12 10000000 208 ns/op 96 B/op 2 allocs/op
BenchmarkListQueue-12 10000000 169 ns/op 96 B/op 2 allocs/op
BenchmarkSliceQueue-12 100000000 25.8 ns/op 82 B/op 0 allocs/op
BenchmarkSliceQueue-12 200000000 12.0 ns/op 83 B/op 0 allocs/op
BenchmarkSliceQueue-12 100000000 10.5 ns/op 82 B/op 0 allocs/op
PASS
ok tinylib/queue/queue_test 13.337s
沒(méi)想到吧，slice 作為隊(duì)列，性能要比 list 好得多，無(wú)論是 CPU 耗時(shí)、內(nèi)存消耗、內(nèi)存申請(qǐng)次數(shù)，slice 到要低，甚至單次操作的 CPU 耗時(shí)僅為 list 的 1⁄20 到 1⁄10 。
你是不是緩過(guò)神來(lái)了，由于雙向鏈表的維護(hù)本身就是需要成本的（維護(hù)前驅(qū)指針和后繼指針），且鏈?zhǔn)浇Y(jié)構(gòu)的內(nèi)存尋址也肯定不如線性結(jié)構(gòu)來(lái)得快的。相比于 list “出棧時(shí)就釋放內(nèi)存，入棧時(shí)才申請(qǐng)內(nèi)存”，slice 的擴(kuò)容策略實(shí)際上是“攢滿了才釋放，避免頻繁 GC，申請(qǐng)時(shí)申請(qǐng)多一點(diǎn)作為預(yù)留，避免頻繁 allocs”，這簡(jiǎn)直成是一個(gè)性能調(diào)優(yōu)的典范呀。
那是不是可以下定論了，用 slice 當(dāng)隊(duì)列比用 list 當(dāng)隊(duì)列性能得多呢？
且慢 again。
換一個(gè)場(chǎng)景再對(duì)比
要知道，性能調(diào)優(yōu)是要考慮具體場(chǎng)景的，在不同的場(chǎng)景，無(wú)謂的性能調(diào)優(yōu)可能會(huì)適得其反。我們換一個(gè)場(chǎng)景測(cè)試上述的例子，這個(gè)場(chǎng)景是：隊(duì)列元素的尺寸比較大。
還是之前的代碼，只是這次隊(duì)列元素不再是一個(gè) int，而是一個(gè)長(zhǎng)度為 1024 的數(shù)組：
import (
"container/list"
"testing"
)
func BenchmarkListQueue(b *testing.B) {
q := list.New()
for i := 0; i < b.N; i++ {
q.PushBack([1024]byte{})
q.PushBack([1024]byte{})
q.Remove(q.Front())
}
}
func BenchmarkSliceQueue(b *testing.B) {
var q [][1024]byte
for i := 0; i < b.N; i++ {
q = append(q, [1024]byte{})
q = append(q, [1024]byte{})
q = q[1:]
}
}再次運(yùn)行：
$ go test -bench=. -benchmem -count=3
goos: darwin
goarch: amd64
pkg: tinylib/queue/queue_test
BenchmarkListQueue-12 2000000 638 ns/op 2144 B/op 4 allocs/op
BenchmarkListQueue-12 3000000 705 ns/op 2144 B/op 4 allocs/op
BenchmarkListQueue-12 3000000 521 ns/op 2144 B/op 4 allocs/op
BenchmarkSliceQueue-12 2000000 4048 ns/op 11158 B/op 0 allocs/op
BenchmarkSliceQueue-12 1000000 3380 ns/op 11003 B/op 0 allocs/op
BenchmarkSliceQueue-12 1000000 2045 ns/op 11003 B/op 0 allocs/op
PASS
ok tinylib/queue/queue_test 23.784s
可以看到，這一次 slice 的性能反過(guò)來(lái)被 list 碾壓了，單次操作所用的 CPU 耗時(shí)是 slice 的三四倍，內(nèi)存使用更是高達(dá)五六倍。
由于元素尺寸比較大，slice 擴(kuò)容時(shí)的元素拷貝操作變成了其性能瓶頸，由于在測(cè)試代碼中，隊(duì)列的長(zhǎng)度會(huì)越來(lái)越長(zhǎng)，所以每次擴(kuò)容需要拷貝的元素也越來(lái)也越多，使得性能越來(lái)越差。所以如果我們?cè)僬{(diào)整一下代碼，讓隊(duì)列中的元素?cái)?shù)量總是保持在一個(gè)較低的數(shù)字，slice 未必就那么容易輸。
總結(jié)
綜上所述，在常規(guī)情況下，slice 因?yàn)槠浣Y(jié)構(gòu)的簡(jiǎn)單，維護(hù)成本低，作為隊(duì)列，性能是勝于 list 的。但如果元素的尺寸越來(lái)越大，隊(duì)列中存儲(chǔ)的元素越來(lái)越多，slice 擴(kuò)容成本也會(huì)隨之越來(lái)越大，當(dāng)超過(guò)一個(gè)臨界值后，便會(huì)在性能上輸給 list。
但事實(shí)上，本文展示了一個(gè)錯(cuò)誤的使用方法，上文中將 [1024]byte 作為隊(duì)列元素時(shí)，你應(yīng)該會(huì)反應(yīng)過(guò)來(lái)，如果換成 *[1024]byte，豈不是會(huì)省去大量的值拷貝操作，大大提升性能？確實(shí)是這樣，如果元素的尺寸確實(shí)需要比較大，可以換成指針類型作為隊(duì)列中的元素，這時(shí)候 slice 就沒(méi)那么容易輸了。
為了證明一下這個(gè)結(jié)論，最后我們祭出 LeetCode 的題：二叉樹(shù)的層次遍歷，一模一樣的解題思路，一個(gè)用 slice，一個(gè)用 list，運(yùn)行結(jié)果如下：
slice：
list：
這里好像 slice 比 list 快了 4 ms，但事實(shí)時(shí)上這么小的時(shí)間差距已經(jīng)沒(méi)有什么可比性的了，稍微抖一抖，多跑幾次，結(jié)果可能就一會(huì)兒 8 ms 一會(huì)兒 4 ms，畢竟測(cè)試用例沒(méi)有真實(shí)地逼出兩種寫法的性能差異，這里只是想說(shuō)明，slice 作隊(duì)列并不會(huì)比 list 挫。
附代碼，寫得不好，將就看哈。
func levelOrder(root *TreeNode) [][]int {
var ret [][]int
if root == nil {
return ret
}
var queue []*TreeNode
queue = append(queue, root)
queue = append(queue, nil)
layer := make([]int, 0)
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node == nil {
ret = append(ret, layer)
layer = make([]int, 0)
if len(queue) > 0 {
queue = append(queue, nil)
}
continue
}
layer = append(layer, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
return ret
}
func levelOrder(root *TreeNode) [][]int {
var ret [][]int
if root == nil {
return ret
}
queue := list.New()
queue.PushBack(root)
queue.PushBack(nil)
layer := make([]int, 0)
for queue.Len() > 0 {
node, ok := queue.Front().Value.(*TreeNode)
queue.Remove(queue.Front())
if !ok {
ret = append(ret, layer)
layer = make([]int, 0)
if queue.Len() > 0 {
queue.PushBack(nil)
}
continue
}
layer = append(layer, node.Val)
if node.Left != nil {
queue.PushBack(node.Left)
}
if node.Right != nil {
queue.PushBack(node.Right)
}
}
return ret
}以上就是golang 中拿slice當(dāng)queue和拿list當(dāng)queue使用分析的詳細(xì)內(nèi)容，更多關(guān)于golang slice queue list的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了深入了解Golang的map增量擴(kuò)容，擴(kuò)容的主要目的是為了縮短map容器的響應(yīng)時(shí)間。增量擴(kuò)容的本質(zhì)其實(shí)就是將總的擴(kuò)容時(shí)間分?jǐn)偟搅嗣恳淮蝖ash操作上，更多相關(guān)內(nèi)容需要的小伙伴可以參考一下2022-06-06
這篇文章主要給大家介紹了關(guān)于go語(yǔ)言中struct標(biāo)簽的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用go語(yǔ)言具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2023-07-07
Golang 標(biāo)準(zhǔn)庫(kù) tips之waitgroup詳解
本篇文章給大家介紹Golang 標(biāo)準(zhǔn)庫(kù) tips之waitgroup的相關(guān)知識(shí)，包括使用 channel 實(shí)現(xiàn) WaitGroup 的功能介紹，感興趣的朋友跟隨小編一起看看吧2021-07-07
這篇文章主要介紹了Go語(yǔ)言聲明一個(gè)多行字符串的變量的方法和示例，非常簡(jiǎn)單實(shí)用，有需要的小伙伴可以參考下。2015-04-04
閉包是一個(gè)函數(shù)和其相關(guān)的引用環(huán)境組合的一個(gè)整體。本文主要為大家介紹一下Go語(yǔ)言中閉包的使用，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Go語(yǔ)言有一定幫助，需要的可以參考一下2022-12-12
Go提供了另一個(gè)重要的數(shù)據(jù)類型,稱為map,它將唯一鍵映射到值,本文主要介紹了Go映射的使用,包括聲明映射、初始化映射、操作映射等,感興趣的可以了解一下2023-11-11
空接口是一種特殊的接口類型,它不包含任何方法,本文主要介紹了go中空接口的具體使用,具有一定的參考價(jià)值,感興趣的可以了解一下2025-04-04
這篇文章主要介紹了Golang 之協(xié)程的用法講解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-04-04
channel[通道]是golang的一種重要特性，正是因?yàn)閏hannel的存在才使得golang不同于其它語(yǔ)言。這篇文章主要介紹了golang開(kāi)發(fā)中channel使用,需要的朋友可以參考下2020-09-09
golang接收post和get請(qǐng)求參數(shù)處理
本文主要介紹了golang接收post和get請(qǐng)求參數(shù)處理，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03