golang中拿slice當queue和拿list當queue使用分析
前言
我記得曾經(jīng)有一次參加面試時，在答題過程中非常嘴欠地說了一句：“我之所以代碼這么寫，因為在 golang 中沒有內(nèi)置的無限長度 queue 的實現(xiàn)……”，當時說完我就后悔了，面試我的人，前幾個問題本就有那么幾分刻薄，一聽這一句，立馬就來勁了：“誰說沒有？誰說沒有？”
好在我連連改口，巧舌如簧，搪塞了過去。我明白，在大牛們的手里，只需最簡單的數(shù)組，稍微加幾個“簡單的”函數(shù)，搖身一變，就可以成為“現(xiàn)成的”隊列、棧、環(huán)、二叉樹、圖……
我不僅不是大牛，我還是個懶漢，我希望的內(nèi)置的隊列，是拿過來就能 dequeue、enqueue 的工具，但 golang 的標準庫里并沒有名字叫 queue 的內(nèi)置對象，只用 channel 可以在某些時候當隊列來用，但是一個 channel 是有長度限制的，超過 channel 的長度了還繼續(xù)入隊會觸發(fā)阻塞，舉個例子：二叉樹的逐層遍歷，第一想到的是用隊列去做吧？但你不知道二叉樹的尺寸，你敢用 channel 懟上去嗎？
網(wǎng)上有很對文章展示了如何自己實現(xiàn)一個隊列，看起來似乎也沒啥問題，但我說了我很懶，我不想自己手寫一個隊列。你說可以把網(wǎng)上的代碼復(fù)制粘貼過來？那我們猜個謎，問：什么實現(xiàn)最有可能需要實現(xiàn)逐層遍歷二叉樹？
答案是：面試的時候。那你是要我面試的時候把把網(wǎng)上的代碼復(fù)制粘貼過來嗎？
……
雖然 golang 沒有內(nèi)置的 queue，但它還是提供了很多強大的數(shù)據(jù)結(jié)構(gòu)，那有沒有可以直接拿過來當 queue 來使的呢？有的，且至少有兩個選項。強調(diào)一句，我們這里并不討論線程安全隊列，僅是普通的無容量限制隊列。
拿 slice 當 queue
我敢打賭，slice 是你在 golang 中用到的最頻繁的數(shù)據(jù)結(jié)構(gòu)了，它基于底層數(shù)組實現(xiàn)的，但又比數(shù)組要強大的多。拿來當隊列用，slice 是完全能勝任的。
初始化一個隊里：
var queue []int
入隊一個元素：
queue = append(queue, 1)
出隊一個元素：
if len(queue) > 1 {
queue = queue[1:]
}看吧，簡單明了，易學易用。
但你會不會有一點覺得 queue = queue[1:] 這樣的寫法有一點挫？白白浪費掉了 slice 前端元素的內(nèi)存，和隊列的假溢出問題有點像，當然 slice 會自動擴容，并不會發(fā)生假溢出，且每次擴容時會重新開辟新數(shù)組，拷貝元素到新數(shù)組時并不會拷貝被棄用的元素，所以內(nèi)存的浪費還是在可控的范圍內(nèi)的。我們可以跑一個例子加以說明：
// 一個空的 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: []
// 入隊一個元素
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]
// 再入隊一個元素
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]
// 出隊一個元素
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]
// 再入隊三個元素
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]
// 出隊二個元素
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]
// 再入隊一個元素，觸發(fā) slise 的擴容，根據(jù)擴容策略，此時 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]不過你可以看到了，當不斷地入隊出隊，slice 的需要反復(fù)擴容，這也可能造成一定的 CPU 消耗。且 queue = queue[1:] 這樣的寫法未免也太簡單粗暴了一點，有沒有更高大上的做法呢，我們且看另一種可以拿來當隊列用的數(shù)據(jù)結(jié)構(gòu)。
拿 list 當 queue
這里的 list 指的是 golang 內(nèi)置的包 container/list，是這是一個雙向鏈表的實現(xiàn)，如果你不了解它，可以花幾分鐘看一下這篇 《container — 容器數(shù)據(jù)類型：heap、list和ring》，這里復(fù)制粘貼一下，把 list 對應(yīng)的方法列舉一下：
type Element
func (e *Element) Next() *Element
func (e *Element) Prev() *Element
type List
func New() *List
func (l *List) Back() *Element // 最后一個元素
func (l *List) Front() *Element // 第一個元素
func (l *List) Init() *List // 鏈表初始化
func (l *List) InsertAfter(v interface{}, mark *Element) *Element // 在某個元素后插入
func (l *List) InsertBefore(v interface{}, mark *Element) *Element // 在某個元素前插入
func (l *List) Len() int // 在鏈表長度
func (l *List) MoveAfter(e, mark *Element) // 把e元素移動到mark之后
func (l *List) MoveBefore(e, mark *Element) // 把e元素移動到mark之前
func (l *List) MoveToBack(e *Element) // 把e元素移動到隊列最后
func (l *List) MoveToFront(e *Element) // 把e元素移動到隊列最頭部
func (l *List) PushBack(v interface{}) *Element // 在隊列最后插入元素
func (l *List) PushBackList(other *List) // 在隊列最后插入接上新隊列
func (l *List) PushFront(v interface{}) *Element // 在隊列頭部插入元素
func (l *List) PushFrontList(other *List) // 在隊列頭部插入接上新隊列
func (l *List) Remove(e *Element) interface{} // 刪除某個元素
當然我們是不用關(guān)心這么多方法的，拿來當隊列用的話，還是很簡單的：
初始化一個隊里：
queue := list.New()
入隊一個元素：
queue.PushBack(1)
出隊一個元素：
if queue.Len() > 1 {
queue.Remove(queue.Front())
}queue.Remove(queue.Front()) 比 queue = queue[1:] 看起來高大上多了有沒有？由于是基于鏈表的，自然也沒有內(nèi)存浪費或假溢出的情況，你是不是已經(jīng)決定好了，以后要用隊列就用它了。
由于不需要像 slice 那樣在擴容時大量拷貝元素，list 作為隊列一定比 slice 性能好得多，難道不是嗎？
性能對比
且慢，口說無憑，我們做個性能測試吧。
測試代碼我已經(jīng)寫好了，測試邏輯是這樣的，每次往隊列里入隊兩個元素，再出隊一個元素，保持隊列的中元素數(shù)量持續(xù)增長。且看代碼：
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:]
}
}運行結(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
沒想到吧，slice 作為隊列，性能要比 list 好得多，無論是 CPU 耗時、內(nèi)存消耗、內(nèi)存申請次數(shù)，slice 到要低，甚至單次操作的 CPU 耗時僅為 list 的 1⁄20 到 1⁄10 。
你是不是緩過神來了，由于雙向鏈表的維護本身就是需要成本的（維護前驅(qū)指針和后繼指針），且鏈式結(jié)構(gòu)的內(nèi)存尋址也肯定不如線性結(jié)構(gòu)來得快的。相比于 list “出棧時就釋放內(nèi)存，入棧時才申請內(nèi)存”，slice 的擴容策略實際上是“攢滿了才釋放，避免頻繁 GC，申請時申請多一點作為預(yù)留，避免頻繁 allocs”，這簡直成是一個性能調(diào)優(yōu)的典范呀。
那是不是可以下定論了，用 slice 當隊列比用 list 當隊列性能得多呢？
且慢 again。
換一個場景再對比
要知道，性能調(diào)優(yōu)是要考慮具體場景的，在不同的場景，無謂的性能調(diào)優(yōu)可能會適得其反。我們換一個場景測試上述的例子，這個場景是：隊列元素的尺寸比較大。
還是之前的代碼，只是這次隊列元素不再是一個 int，而是一個長度為 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:]
}
}再次運行：
$ 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 的性能反過來被 list 碾壓了，單次操作所用的 CPU 耗時是 slice 的三四倍，內(nèi)存使用更是高達五六倍。
由于元素尺寸比較大，slice 擴容時的元素拷貝操作變成了其性能瓶頸，由于在測試代碼中，隊列的長度會越來越長，所以每次擴容需要拷貝的元素也越來也越多，使得性能越來越差。所以如果我們再調(diào)整一下代碼，讓隊列中的元素數(shù)量總是保持在一個較低的數(shù)字，slice 未必就那么容易輸。
總結(jié)
綜上所述，在常規(guī)情況下，slice 因為其結(jié)構(gòu)的簡單，維護成本低，作為隊列，性能是勝于 list 的。但如果元素的尺寸越來越大，隊列中存儲的元素越來越多，slice 擴容成本也會隨之越來越大，當超過一個臨界值后，便會在性能上輸給 list。
但事實上，本文展示了一個錯誤的使用方法，上文中將 [1024]byte 作為隊列元素時，你應(yīng)該會反應(yīng)過來，如果換成 *[1024]byte，豈不是會省去大量的值拷貝操作，大大提升性能？確實是這樣，如果元素的尺寸確實需要比較大，可以換成指針類型作為隊列中的元素，這時候 slice 就沒那么容易輸了。
為了證明一下這個結(jié)論，最后我們祭出 LeetCode 的題：二叉樹的層次遍歷，一模一樣的解題思路，一個用 slice，一個用 list，運行結(jié)果如下：
slice：
list：
這里好像 slice 比 list 快了 4 ms，但事實時上這么小的時間差距已經(jīng)沒有什么可比性的了，稍微抖一抖，多跑幾次，結(jié)果可能就一會兒 8 ms 一會兒 4 ms，畢竟測試用例沒有真實地逼出兩種寫法的性能差異，這里只是想說明，slice 作隊列并不會比 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當queue和拿list當queue使用分析的詳細內(nèi)容，更多關(guān)于golang slice queue list的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了Go語言編程中字符串切割方法小結(jié),所整理的方法都來自字符串相關(guān)的strings包,需要的朋友可以參考下2015-10-10
本文給大家介紹Go語言中nil判斷的注意事項,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧2025-06-06
這篇文章主要介紹了Go 中 slice 的 In 功能實現(xiàn)探索,本文通過實例代碼給大家介紹的非常詳細，具有一定的參考借鑒價值，需要的朋友可以參考下2019-09-09
這篇文章主要介紹了調(diào)試利器?go-spew,go-spew?可以以一種非常友好的方式輸出完整的數(shù)據(jù)結(jié)構(gòu)信息，go-spew?支持一些自定義配置，可以通過?spew.Config?修改，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
本文將從一個資源回收問題引入，引出defer關(guān)鍵字，并對其進行基本介紹，從而讓大家對Go語言中的defer有更深入的了解，需要的小伙伴可以學習一下2023-05-05
這篇文章主要為大家詳細介紹了Golang中有關(guān)循環(huán)處理map時的性能優(yōu)化,本文主要介紹了常見的三種場景,文中的示例代碼講解詳細,需要的可以了解下2025-05-05
這篇文章主要介紹了Go語言聲明一個多行字符串的變量的方法和示例，非常簡單實用，有需要的小伙伴可以參考下。2015-04-04
這篇文章主要介紹了詳解go語言中type的幾種使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-02-02
這篇文章主要為大家介紹了Golang?流水線設(shè)計模式實踐示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-12-12
Go語言保證了既能到達靜態(tài)編譯語言的安全和性能，又達到了動態(tài)語言開發(fā)速度和易維護性，有人形容Go語言：Go=?C?+?Python?,?說明Go語言既有C靜態(tài)語言程序的運行速度，又能達到Python動態(tài)語言的快速開發(fā)，這篇文章主要介紹了Go介紹和環(huán)境配置,需要的朋友可以參考下2022-07-07