Golang 中拿 slice、list 做 queue 的異同
【導讀】Go 項目中的隊列要用什麼數據結構實現？怎麼做更高效？本文做了詳細介紹。
前言
我記得曾經有一次參加面試時，在答題過程中非常嘴欠地說了一句：“我之所以代碼這麼寫，因爲在 golang 中沒有內置的無限長度 queue 的實現……”，當時說完我就後悔了，面試我的人，前幾個問題本就有那麼幾分刻薄，一聽這一句，立馬就來勁了：“誰說沒有？誰說沒有？”
好在我連連改口，巧舌如簧，搪塞了過去。我明白，在大牛們的手裏，只需最簡單的數組，稍微加幾個 “簡單的” 函數，搖身一變，就可以成爲 “現成的” 隊列、棧、環、二叉樹、圖……
我不僅不是大牛，我還是個懶漢，我希望的內置的隊列，是拿過來就能 dequeue、enqueue 的工具，但 golang 的標準庫裏並沒有名字叫 queue 的內置對象，只用 channel 可以在某些時候當隊列來用，但是一個 channel 是有長度限制的，超過 channel 的長度了還繼續入隊會觸發阻塞，舉個例子：二叉樹的逐層遍歷，第一想到的是用隊列去做吧？但你不知道二叉樹的尺寸，你敢用 channel 懟上去嗎？
網上有很對文章展示瞭如何自己實現一個隊列，看起來似乎也沒啥問題，但我說了我很懶，我不想自己手寫一個隊列。你說可以把網上的代碼複製粘貼過來？那我們猜個謎，問：什麼實現最有可能需要實現逐層遍歷二叉樹？
答案是：面試的時候。那你是要我面試的時候把把網上的代碼複製粘貼過來嗎？
……
雖然 golang 沒有內置的 queue，但它還是提供了很多強大的數據結構，那有沒有可以直接拿過來當 queue 來使的呢？有的，且至少有兩個選項。強調一句，我們這裏並不討論線程安全隊列，僅是普通的無容量限制隊列。
拿 slice 當 queue
我敢打賭，slice 是你在 golang 中用到的最頻繁的數據結構了，它基於底層數組實現的，但又比數組要強大的多。拿來當隊列用，slice 是完全能勝任的。
初始化一個隊裏：
var queue []int入隊一個元素：
queue = append(queue, 1)出隊一個元素：
if len(queue) > 1 {
queue = queue[1:]
}看吧，簡單明瞭，易學易用。
但你會不會有一點覺得 queue = queue[1:] 這樣的寫法有一點挫？白白浪費掉了 slice 前端元素的內存，和隊列的假溢出問題有點像，當然 slice 會自動擴容，並不會發生假溢出，且每次擴容時會重新開闢新數組，拷貝元素到新數組時並不會拷貝被棄用的元素，所以內存的浪費還是在可控的範圍內的。我們可以跑一個例子加以說明：
// 一個空的 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]
// 再入隊一個元素，觸發 slise 的擴容，根據擴容策略，此時 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 的需要反覆擴容，這也可能造成一定的 CPU 消耗。且 queue = queue[1:] 這樣的寫法未免也太簡單粗暴了一點，有沒有更高大上的做法呢，我們且看另一種可以拿來當隊列用的數據結構。
拿 list 當 queue
這裏的 list 指的是 golang 內置的包 container/list，是這是一個雙向鏈表的實現，如果你不瞭解它，可以花幾分鐘看一下這篇 《container — 容器數據類型：heap、list 和 ring》，這裏複製粘貼一下，把 list 對應的方法列舉一下：
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{} // 刪除某個元素當然我們是不用關心這麼多方法的，拿來當隊列用的話，還是很簡單的：
初始化一個隊裏：
queue := list.New()入隊一個元素：
queue.PushBack(1)出隊一個元素：
if queue.Len() > 1 {
queue.Remove(queue.Front())
}queue.Remove(queue.Front()) 比 queue = queue[1:] 看起來高大上多了有沒有？由於是基於鏈表的，自然也沒有內存浪費或假溢出的情況，你是不是已經決定好了，以後要用隊列就用它了。
由於不需要像 slice 那樣在擴容時大量拷貝元素，list 作爲隊列一定比 slice 性能好得多，難道不是嗎？
性能對比
且慢，口說無憑，我們做個性能測試吧。
測試代碼我已經寫好了，測試邏輯是這樣的，每次往隊列裏入隊兩個元素，再出隊一個元素，保持隊列的中元素數量持續增長。且看代碼：
import (
"container/list"
"testing"
)
func BenchmarkListQueue(b *testing.B) {
q := list.New()
for i := 0; i < b.N; i++ {
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 = q[1:]
}
}運行結果：
$ 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 耗時、內存消耗、內存申請次數，slice 到要低，甚至單次操作的 CPU 耗時僅爲 list 的 1⁄20 到 1⁄10 。
你是不是緩過神來了，由於雙向鏈表的維護本身就是需要成本的（維護前驅指針和後繼指針），且鏈式結構的內存尋址也肯定不如線性結構來得快的。相比於 list “出棧時就釋放內存，入棧時才申請內存”，slice 的擴容策略實際上是 “攢滿了才釋放，避免頻繁 GC，申請時申請多一點作爲預留，避免頻繁 allocs”，這簡直成是一個性能調優的典範呀。
那是不是可以下定論了，用 slice 當隊列比用 list 當隊列性能得多呢？
且慢 again。
換一個場景再對比
要知道，性能調優是要考慮具體場景的，在不同的場景，無謂的性能調優可能會適得其反。我們換一個場景測試上述的例子，這個場景是：隊列元素的尺寸比較大。
還是之前的代碼，只是這次隊列元素不再是一個 int，而是一個長度爲 1024 的數組：
import (
"container/list"
"testing"
)
func BenchmarkListQueue(b *testing.B) {
q := list.New()
for i := 0; i < b.N; i++ {
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 = 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 的三四倍，內存使用更是高達五六倍。
由於元素尺寸比較大，slice 擴容時的元素拷貝操作變成了其性能瓶頸，由於在測試代碼中，隊列的長度會越來越長，所以每次擴容需要拷貝的元素也越來也越多，使得性能越來越差。所以如果我們再調整一下代碼，讓隊列中的元素數量總是保持在一個較低的數字，slice 未必就那麼容易輸。
總結
綜上所述，在常規情況下，slice 因爲其結構的簡單，維護成本低，作爲隊列，性能是勝於 list 的。但如果元素的尺寸越來越大，隊列中存儲的元素越來越多，slice 擴容成本也會隨之越來越大，當超過一個臨界值後，便會在性能上輸給 list。
但事實上，本文展示了一個錯誤的使用方法，上文中將 [1024]byte 作爲隊列元素時，你應該會反應過來，如果換成 *[1024]byte，豈不是會省去大量的值拷貝操作，大大提升性能？確實是這樣，如果元素的尺寸確實需要比較大，可以換成指針類型作爲隊列中的元素，這時候 slice 就沒那麼容易輸了。
爲了證明一下這個結論，最後我們祭出 LeetCode 的題：二叉樹的層次遍歷，一模一樣的解題思路，一個用 slice，一個用 list，運行結果如下：
slice：
image
list：
image
這裏好像 slice 比 list 快了 4 ms，但事實時上這麼小的時間差距已經沒有什麼可比性的了，稍微抖一抖，多跑幾次，結果可能就一會兒 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
}轉自：
blog.wolfogre.com/posts/slice-queue-vs-list-queue/
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/GCzzkUJLWMOCSJDxCpojRg