前言

我記得曾經(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)上的代碼復制粘貼過來？那我們猜個謎，問：什么實現(xiàn)最有可能需要實現(xiàn)逐層遍歷二叉樹？

答案是：面試的時候。那你是要我面試的時候把把網(wǎng)上的代碼復制粘貼過來嗎？

……

雖然 golang 沒有內(nèi)置的 queue，但它還是提供了很多強大的數(shù)據(jù)結(jié)構，那有沒有可以直接拿過來當 queue 來使的呢？有的，且至少有兩個選項。強調(diào)一句，我們這里并不討論線程安全隊列，僅是普通的無容量限制隊列。

拿 slice 當 queue

我敢打賭，slice 是你在 golang 中用到的最頻繁的數(shù)據(jù)結(jié)構了，它基于底層數(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 的需要反復擴容，這也可能造成一定的 CPU 消耗。且 queue = queue[1:] 這樣的寫法未免也太簡單粗暴了一點，有沒有更高大上的做法呢，我們且看另一種可以拿來當隊列用的數(shù)據(jù)結(jié)構。

拿 list 當 queue

這里的 list 指的是 golang 內(nèi)置的包 container/list，是這是一個雙向鏈表的實現(xiàn)，如果你不了解它，可以花幾分鐘看一下這篇 《container — 容器數(shù)據(jù)類型：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:] 看起來高大上多了有沒有？由于是基于鏈表的，自然也沒有內(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é)構的內(nèi)存尋址也肯定不如線性結(jié)構來得快的。相比于 list “出棧時就釋放內(nèi)存，入棧時才申請內(nèi)存”，slice 的擴容策略實際上是“攢滿了才釋放，避免頻繁 GC，申請時申請多一點作為預留，避免頻繁 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é)構的簡單，維護成本低，作為隊列，性能是勝于 list 的。但如果元素的尺寸越來越大，隊列中存儲的元素越來越多，slice 擴容成本也會隨之越來越大，當超過一個臨界值后，便會在性能上輸給 list。

但事實上，本文展示了一個錯誤的使用方法，上文中將 [1024]byte 作為隊列元素時，你應該會反應過來，如果換成 *[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)容，更多關于golang slice queue list的資料請關注腳本之家其它相關文章！

最新評論