Go 切片與技巧（附圖解）

你好，我是太白，今天和你聊聊 Go 語言的切片（Slice）以及它的一些技巧。

1 前言

切片是 Go 語言中最多被使用的數據結構之一。本文將介紹切片的創建、操作、表達式以及使用的技巧。

2 數組

slice 類型是建立在 Go 的數組類型之上的抽象，因此要理解 slice，我們必須首先理解數組。

先看一段代碼：

 var a [4]int // 數組類型: 定義指定長度和元素類型
 a[0] = 1     // 數組a的第一個索引的值設置爲1
 i := a[0]
 fmt.Println(i)    // 輸出：1， 說明已經設置成功
 fmt.Println(a[1]) // 輸出：0，說明數組不需要顯式初始化，其元素本身爲零
 fmt.Println(a[4]) // 報錯：invalid array index 4 (out of bounds for 4-element array)

（代碼來自 Go Slices: usage and internals[1]）

說明：

1、代碼中 var a [4]int 完成了數組的初始化，表示一個由四個整數組成的數組。
2、默認值爲 0。當我們打印a[1]的時候輸出 0。
3、設置數組索引的值，可以直接指定下標的索引進行賦值，例子中是a[0] = 1。
3、Go 數組的索引和其他語言一樣，從 0 開始，數組的大小是固定的，上面例子中最大是 4 的的大小，所以下標索引最大是 3，所以當我們訪問a[4]會報數組越界的錯誤。

Go的數組是值類型。不像 C 語言數組變量是指向第一個元素的指針，所以當我們把數組變量傳遞或者賦值的時候，其實是做 copy 的操作。比如下面的例子 a 賦值給 b，修改 a 中的元素，並沒有影響 b 中的元素：

 a := [2]string{"johnny", "太白技術"} // 長度`2`，可以改成`...`，編譯器會自動計算數組的長度
 b := a
 a[0] = "xujiajun"
 fmt.Println(a) // 輸出：[xujiajun 太白技術]
 fmt.Println(b) // 輸出：[johnny 太白技術]

爲了避免複製，你可以傳遞一個指向數組的指針，例如：

func double(arr *[3]int) {
 for i, num := range *arr {
  (*arr)[i] = num * 2
 }
}
a := [3]int{1, 2, 3}
double(&a)
fmt.Println(a) // [2 4 6]

（代碼參考 Effective Go[2]）

3 切片的創建

由於數組需要固定長度，很多時候不是很靈活，而切片更靈活、更強大。切片包含對底層數組的引用，如果將一個切片分配給另一個切片，則兩者都引用同一個數組。

切片底層的數據結構（src/runtime/slice.go）：

type slice struct {
 array unsafe.Pointer // 指針指向底層數組
 len   int  // 切片長度
 cap   int  // 底層數組容量
}

切片的類型規範是 []T，其中 T 是切片元素的類型。與數組類型不同，切片類型沒有指定長度。

創建切片有多種方式：變量聲明、切片字面量、make創建、new創建、從切片/數組截取。

1、變量聲明

 var s []byte

這種聲明的切片變量，默認值是 nil，容量和長度默認都是 0。

 var x []byte
 fmt.Println(cap(x))   // 0
 fmt.Println(len(x))   // 0
 fmt.Println(x == nil) // true

2、切片字面量

當使用字面量來聲明切片時，其語法與使用字面量聲明數組非常相似：

a := []string{"johnny", "太白技術"} // 這是切片聲明，少了長度的指定
b := [2]string{"johnny", "太白技術"} // 這是數組聲明，多了長度的指定

3、make 創建：

除了上面創建方式外，使用內置函數make可以指定長度和容量來創建（具體函數：func make([]T, len, cap) []T）

其中 T 代表要創建的切片的元素類型。該 make 函數採用類型、長度和可選容量。調用時，make 分配一個數組並返回一個引用該數組的切片。

首先看下空切片：

 y := make([]int, 0)
 fmt.Println(cap(y))   // 0
 fmt.Println(len(y))   // 0
 fmt.Println(y == nil) // false

下面這個例子中創建了長度爲 5，容量等於 5 的切片

 var s []byte
 s = make([]byte, 5, 5) // 指定了長度和容量
 fmt.Println(s) // 輸出：[0 0 0 0 0]

當容量參數被省略時，它默認爲指定的長度：

s := make([]byte, 5)
fmt.Println(s) // 輸出也是 [0 0 0 0 0]

內置 len 和 cap 函數檢查切片的長度和容量：

 fmt.Println(len(s)) // 5
 fmt.Println(cap(s)) // 5

4、使用 new

使用 new 創建的切片是個 nil 切片。

 n := *new([]int)
 fmt.Println(n == nil) // true

5、從切片 / 數組截取

切片可以基於數組和切片來創建。這邊會用到切片表達式，3.3 會詳細說明。

 n := [5]int{1, 2, 3, 4, 5}
 n1 := n[1:]     // 從n數組中截取
 fmt.Println(n1) // [2 3 4 5]
 n2 := n1[1:]    // 從n1切片中截取
 fmt.Println(n2) // [3 4 5]

切片與原數組或切片是共享底層空間的，接着上面例子，把 n2 的元素修改之後，會影響原切片和數組：

 n2[1] = 6 // 修改n2，會影響原切片和數組
 fmt.Println(n1) // [2 3 6 5]
 fmt.Println(n2) // [3 6 5]
 fmt.Println(n)  // [1 2 3 6 5]

4 切片操作

內置函數append()用於向切片中追加元素。

 n := make([]int, 0)
 n = append(n, 1)                 // 添加一個元素
 n = append(n, 2, 3, 4)           // 添加多個元素
 n = append(n, []int{5, 6, 7}...) // 添加一個切片
 fmt.Println(n)                   // [1 2 3 4 5 6 7]

當 append 操作的時候，切片容量如果不夠，會觸發擴容，接着上面的例子：

 fmt.Println(cap(n)) // 容量等於8
 n = append(n, []int{8, 9, 10}...)
 fmt.Println(cap(n)) // 容量等於16，發生了擴容

當一開始容量是 8，後面追加了切片 []int{8, 9, 10} 之後，容量變成了 16。關於詳細的擴容機制，我們後面文章再聊。

5 切片表達式

Go 語言提供了兩種切片的表達式：

1、簡單表達式
2、擴展表達式

1、簡單的表達式

簡單切片表達式的格式[low:high]。

如下面例子，n 爲一個切片，當用這個表達式[1:4]表示的是左閉右開[low, high)區間截取一個新的切片（例子中結果是 [2 3 4]），切片被截取之後，截取的長度是high-low。

 n := []int{1, 2, 3, 4, 5, 6}
 fmt.Println(n[1:4])      // [2 3 4]

切片表達式的開始 low 和結束索引 high 是可選的；它們分別默認爲零和切片的長度：

n := []int{1, 2, 3, 4, 5, 6}
fmt.Println(n[:4])      // [1 2 3 4]，:前面沒有值，默認表示0
fmt.Println(n[1:])       // [2 3 4 5 6]，:後面沒有值，默認表示切片的長度

邊界問題

1、當 n 爲數組或字符串表達式 n[low:high] 中 low 和 high 的取值關係：

0 <= low <=high <= len(n)

2、當 n 爲切片的時候，表達式 n[low:high] 中 high 最大值變成了 cap(n)，low 和 high 的取值關係：

0 <= low <=high <= cap(n)

不滿足以上條件會發送越界 panic。

截取字符串

注意截取字符串，產生的也是新的字符串。

 s := "hello taibai"
 s1 := s[6:]
 fmt.Println(s1)                 // taibai
 fmt.Println(reflect.TypeOf(s1)) // string

2、擴展表達式

簡單表達式生產的新切片與原數組或切片會共享底層數組，雖然避免了 copy，但是會帶來一定的風險。下面這個例子當新的 n1 切片 append 添加元素的時候，覆蓋了原來 n 的索引位置 4 的值，導致你的程序可能是非預期的，從而產生不良的後果。

 n := []int{1, 2, 3, 4, 5, 6}
 n1 := n[1:4]
 fmt.Println(n)       // [1 2 3 4 5 6]
 fmt.Println(n1)      // [2 3 4]
 n1 = append(n1, 100) // 把n的索引位置4的值從原來的5變成了100
 fmt.Println(n)       // [1 2 3 4 100 6]

Go 1.2[3] 中提供了一種可以限制新切片容量的表達式：

n[low:high:max]

max 表示新生成切片的容量，新切片容量等於max-low，表達式中 low、high、max 關係：

0 <= low <= high <= max <= cap(n)

繼續剛纔的例子，當計算n[1:4]的容量，用 cap 得到值等於 5，用擴展表達式n[1:4:5]，用 cap 重新計算得到新的容量值（5-1）等於 4：

 fmt.Println(cap(n[1:4])) // 5
 fmt.Println(cap(n[1:4:5])) // 4

關於容量

n[1:4] 的長度是 3 好理解（4-1），容量爲什麼是 5？

因爲切片 n[1:4] 和切片 n 是共享底層空間，所以它的容量並不等於他的長度 3，根據 1 等於索引 1 的位置（等於值 2），從值 2 這個元素開始到末尾元素 6，共 5 個，所以n[1:4]容量是 5。

如果 append 超過切片的長度會重新生產一個全新的切片，不會覆蓋原來的：

 n2 := n[1:4:5]         // 長度等於3，容量等於4
 fmt.Printf("%p\n", n2) // 0xc0000ac068
 n2 = append(n2, 5)
 fmt.Printf("%p\n", n2) // 0xc0000ac068
 n2 = append(n2, 6)
 fmt.Printf("%p\n", n2) // 地址發生改變，0xc0000b8000

6 切片技巧

Go 在 Github 的官方 Wiki 上介紹了切片的技巧 SliceTricks[4]，另外這個項目 Go Slice Tricks Cheat Sheet[5] 基於 SliceTricks 做了一系列的圖，比較直觀。Go Slice Tricks Cheat Sheet 做的圖有些缺失，我也做了補充

說明：官方 Wiki 最後更新時間是 2022.1.22，下文是基於這個版本來描述。

AppendVector

這個是添加一個切片的操作，上面我們在切片操作中已經介紹過。

a = append(a, b...)

Copy

這邊給我們展示了三種 copy 的寫法：

b := make([]T, len(a))
copy(b, a)

// 效率一般比上面的寫法慢，但是如果有更多，他們效率更好
b = append([]T(nil), a...)
b = append(a[:0:0], a...)

// 這個實現等價於make+copy。
// 但在Go工具鏈v1.16上實際上會比較慢。
b = append(make([]T, 0, len(a)), a...)

Cut

截掉切片[i,j）之間的元素：

a = append(a[:i], a[j:]...)

Cut（GC）

上面的Cut如果元素是指針的話，會存在內存泄露，所以我們要對刪除的元素設置nil，等待 GC。

copy(a[i:], a[j:])
for k, n := len(a)-j+i, len(a); k < n; k++ {
 a[k] = nil // or the zero value of T
}
a = a[:len(a)-j+i]

Delete

刪除索引位置 i 的元素：

a = append(a[:i], a[i+1:]...)
// or
a = a[:i+copy(a[i:], a[i+1:])]

Delete（GC）

刪除索引位置 i 的元素：

copy(a[i:], a[i+1:])
a[len(a)-1] = nil // or the zero value of T
a = a[:len(a)-1]

Delete without preserving order

刪除索引位置 i 的元素，把最後一位放到索引位置 i 上，然後把最後一位元素刪除。這種方式底層並沒有發生複製操作。

a[i] = a[len(a)-1] 
a = a[:len(a)-1]

Delete without preserving order（GC）

上面的刪除操作，元素是一個指針的類型或結構體指針字段，會存在最後一個元素不能被 GC 掉，造成泄露，把末尾的元素設置 nil，等待 GC。

a[i] = a[len(a)-1]
a[len(a)-1] = nil
a = a[:len(a)-1]

Expand

這個本質上是多個 append 的組合操作。

a = append(a[:i], append(make([]T, j), a[i:]...)...)

Extend

用新列表擴展原來的列表

a = append(a, make([]T, j)...)

Filter (in place)

下面代碼演示原地刪除 Go 切片元素：

n := 0
for _, x := range a {
 if keep(x) {
  a[n] = x
  n++
 }
}
a = a[:n]

Insert

a = append(a[:i], append([]T{x}, a[i:]...)...)

第二個append會產生新的切片，產生一次 copy，可以用以下代碼方式，可免去第二次的 copy：

s = append(s, 0 /* 先添加一個0值*/)
copy(s[i+1:], s[i:])
s[i] = x

InsertVector

下面代碼演示插入向量（封裝了動態大小數組的順序容器）的實現：

a = append(a[:i], append(b, a[i:]...)...)

func Insert(s []int, k int, vs ...int) []int {
 if n := len(s) + len(vs); n <= cap(s) {
  s2 := s[:n]
  copy(s2[k+len(vs):], s[k:])
  copy(s2[k:], vs)
  return s2
 }
 s2 := make([]int, len(s) + len(vs))
 copy(s2, s[:k])
 copy(s2[k:], vs)
 copy(s2[k+len(vs):], s[k:])
 return s2
}

a = Insert(a, i, b...)

Push

a = append(a, x)

Pop

 x, a = a[len(a)-1], a[:len(a)-1]

Push Front/Unshift

a = append([]T{x}, a...)

Pop Front/Shift

x, a = a[0], a[1:]

7 切片額外技巧

Filtering without allocating

下面例子演示數據過濾的時候，b 基於原來的 a 存儲空間來操作，並沒有重新生成新的存儲空間。

b := a[:0]
for _, x := range a {
 if f(x) {
  b = append(b, x)
 }
}

爲了讓截取之後沒有使用的存儲被 GC 掉，需要設置成 nil：

for i := len(b); i < len(a); i++ {
 a[i] = nil // or the zero value of T
}

Reversing

反轉操作演示：

for i := len(a)/2-1; i >= 0; i-- {
 opp := len(a)-1-i
 a[i], a[opp] = a[opp], a[i]
}

還有一種方法：

for left, right := 0, len(a)-1; left < right; left, right = left+1, right-1 {
 a[left], a[right] = a[right], a[left]
}

Shuffling

洗牌算法。算法思想就是從原始數組中隨機抽取一個新的數字到新數組中。

for i := len(a) - 1; i > 0; i-- {
    j := rand.Intn(i + 1)
    a[i], a[j] = a[j], a[i]
}

go1.10 之後有內置函數 Shuffle[6]

Batching with minimal allocation

做批處理大的切片的時候，這個技巧可以瞭解下：

actions := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
batchSize := 3
batches := make([][]int, 0, (len(actions) + batchSize - 1) / batchSize)

for batchSize < len(actions) {
    actions, batches = actions[batchSize:], append(batches, actions[0:batchSize:batchSize])
}
batches = append(batches, actions)

// 結果：
// [[0 1 2] [3 4 5] [6 7 8] [9]]

In-place deduplicate (comparable)

刪除有序數組中的重複項：

import "sort"

in := []int{3,2,1,4,3,2,1,4,1} // any item can be sorted
sort.Ints(in)
j := 0
for i := 1; i < len(in); i++ {
 if in[j] == in[i] {
  continue
 }
 j++
 // preserve the original data
 // in[i], in[j] = in[j], in[i]
 // only set what is required
 in[j] = in[i]
}
result := in[:j+1]
fmt.Println(result) // [1 2 3 4]

Move to front, or prepend if not present, in place if possible.

下面代碼演示移動指定元素到頭部：

// moveToFront moves needle to the front of haystack, in place if possible.
func moveToFront(needle string, haystack []string) []string {
 if len(haystack) != 0 && haystack[0] == needle {
  return haystack
 }
 prev := needle
 for i, elem := range haystack {
  switch {
  case i == 0:
   haystack[0] = needle
   prev = elem
  case elem == needle:
   haystack[i] = prev
   return haystack
  default:
   haystack[i] = prev
   prev = elem
  }
 }
 return append(haystack, prev)
}

haystack := []string{"a", "b", "c", "d", "e"} // [a b c d e]
haystack = moveToFront("c", haystack)         // [c a b d e]
haystack = moveToFront("f", haystack)         // [f c a b d e]

Sliding Window

下面實現根據 size 的滑動窗口輸出：

func slidingWindow(size int, input []int) [][]int {
 // returns the input slice as the first element
 if len(input) <= size {
  return [][]int{input}
 }

 // allocate slice at the precise size we need
 r := make([][]int, 0, len(input)-size+1)

 for i, j := 0, size; j <= len(input); i, j = i+1, j+1 {
  r = append(r, input[i:j])
 }

 return r
}

func TestSlidingWindow(t *testing.T) {
 result := slidingWindow(2, []int{1, 2, 3, 4, 5})
 fmt.Println(result) // [[1 2] [2 3] [3 4] [4 5]]
}

總結

1、Go 切片本質上是一個結構體，保存了其長度、底層數組的容量、底層數組的指針。
2、Go 切片創建方式比較多樣：變量聲明、切片字面量、make創建、new創建、從切片/數組截取。
3、Go 切片使用len()計算長度、cap()計算容量、append()來添加元素。
4、Go 切片相比數組更靈活，有很多技巧，也正因爲靈活，容易發生類似內存泄露的問題，需要注意。

參考資料

[1]

Go Slices: usage and internals: https://go.dev/blog/slices-intro

[2]

Effective Go: https://go.dev/doc/effective_go#arrays

[3]

go1.2#three_index: https://tip.golang.org/doc/go1.2#three_index

[4]

SliceTricks: https://github.com/golang/go/wiki/SliceTricks

[5]

Go Slice Tricks Cheat Sheet: https://ueokande.github.io/go-slice-tricks/

[6]

Shuffle: https://pkg.go.dev/math/rand#Shuffle

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/pNfx7AtXg_SiapWEG1w8gw