2. 数组上: 深入理解 slice

  • Go 数据结构与算法系列文章,本系列文章主要会包括常见的数据结构与算法实现,同时会包括 Go 标准库代码的分析理解,讲到对应章节的时候优先学习分析 Go 的源码实现,例如 slice、list、sort 等,然后可能会有一些常见的案例实现,同时这也是 极客时间-数据结构与算法之美 的课程笔记
  • 本文代码仓库: https://github.com/mohuishou/go-algorithm 🌟🌟🌟🌟🌟
  • RoadMap: 持续更新中,预计一周更新 1 ~ 2 篇文章,预计到 202101 月底前更新完成
  • 获取更新: Github知乎RSS开发者头条
  • 上一个系列刚刚完成了 Go 设计模式,如果感兴趣也可以进行查看

上期答案

Q: 通过 Element 节点中的 List 结构来判断节点是否属于当前链表的方式,在某些情况下会出现 bug

1
2
3
4
5
6
l := list.List{}
e := l.PushBack(10)

l = list.List{}
l.Remove(e)
fmt.Println("list len: ", l.Len())

接着看下面之前,先想一想,你觉得这段代码会输出什么?
这个问题来自: https://github.com/golang/go/issues/39014
这段代码会输出 -1,但是我们期望的不应该是输出 0 么?
我们来看看发生了什么?
01_链表.drawio.svg

  • 当我们执行完 l.PushBack(10) 这段代码直接,就如左图所示了,节点 e 指向了链表 l,链表 l 的值的长度是 1
  • 但是当我们执行完 l = list.List{} 我们重置了链表 l 的值,并没有修改他的地址,所以 e 还是指向的链表 l,当执行 Remove 方法的时候,e 的链表和当前执行的 l 的地址判断是可以对应的上的,但是实际上链表的值已经发生了变化,链表的长度已经不为 1 的,并且新的链表的根节点也没有指向 e
  • 所以最后得到的长度才是 -1
  • 最后细心的同学应该已经发现,这里其实还可能存在内存泄漏的问题,元素 e -> root(0x2) 其实已经没有用到了

什么是数组?

  • 数组大家应该都非常属性我们来简单的回顾一下
  • 数组是一个具有连续的内存空间和相同类型的数据的数据结构
  • 我们随机访问任意一个下标的数据的时间复杂度都是 O(1)
  • 但是正是由于这种特性,导致它插入和删除元素的效率比较低,是 O(n)

01_array.drawio.svg

Go 中的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func main() {
// 初始化数组
var arr = [3]int{1, 2, 3}
// 查找元素
fmt.Printf("arr[1]: %d\n", arr[1])
// 删除元素
remove(&arr, 2)
// remove(&arr, 3) // will panic
fmt.Println(arr)
}

// 删除数组 arr 的某个元素
// index 为需要删除的索引
// 从需要删除的元素开始,依次将后面的元素往前移动一位即可
// 然后将最后一位修改为该类型的默认值
func remove(arr *[3]int, index int) {
if index >= len(arr) {
log.Panicf("%d remove out range arr", index)
}
for i := index; i < len(arr)-1; i++ {
arr[i] = arr[i+1]
}
arr[len(arr)-1] = 0
}

Q: 为什么我们在 remove 函数当中的参数使用的是指针

这是因为在 go 中参数的传递都是值传递,如果不用指针的话,那么就会复制一份数据到函数中,这样就无法做到删除的作用

1
2
3
4
5
6
7
8
9
10
11
12
// 在函数 main 中
fmt.Printf("main: %p --> %+v\n", &arr, arr)
p(arr)
p2(&arr)

func p(arr [3]int) {
fmt.Printf("p: %p --> %+v\n", &arr, arr)
}

func p2(arr *[3]int) {
fmt.Printf("p2: %p --> %+v\n", arr, arr)
}

输出:

1
2
3
main: 0xc0000c2000 --> [1 2 0]
p: 0xc0000c2080 --> [1 2 0]
p2: 0xc0000c2000 --> &[1 2 0]

通过上面的例子我们就可以发现,在函数 p 中我们直接传递的数组,最后打印的变量地址是和 main 中不同的,就印证了我们之前的说法
在实际使用过程中,我们其实是很少使用到固定长度的数组的,而是使用可以自动扩容的 slice,接下来我们就深入的看一下 slice 当中的一些细节

深入理解 Slice

使用

基础使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 初始化
s1 := make([]int, 2)
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", &s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [0 0], len: 2, cap: 2

// 赋值
s1[0] = 1
s1[1] = 2
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", &s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [1 2], len: 2, cap: 2

// 扩容
s1 = append(s1, 3)
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", &s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [1 2 3], len: 3, cap: 4

// 删除元素
s1 = append(s1[:1], s1[2:]...)
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", &s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [1 3], len: 2, cap: 4
  • 可以发现,通过 append 之后 s1 的容量和长度都发生了变化,说明完成了自动扩容
  • 删除元素之后我们的长度发生了变化,但是容量还是原本不变

常见坑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 复制一个 slice
s2 := s1[:2]
fmt.Printf("s2(%p): %v, len: %d, cap: %d\n", &s2, s2, len(s2), cap(s2))
// s2(0xc00000c120): [1 3], len: 2, cap: 4

s1[0] = 10 // 这里可以发现,s1[0] s2[0] 都被修改为了 10
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", &s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [10 3], len: 2, cap: 4
fmt.Printf("s2(%p): %v, len: %d, cap: %d\n", &s2, s2, len(s2), cap(s2))
// s2(0xc00000c120): [10 3], len: 2, cap: 4

s1 = append(s1, 5, 6, 7, 8)
s1[0] = 11 // 这里可以发现,s1[0] 被修改为了 11, s2[0] 还是10
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", &s1, s1, len(s1), cap(s1))
// s1(0xc00011c020): [11 3 5 6 7 8], len: 6, cap: 8
fmt.Printf("s2(%p): %v, len: %d, cap: %d\n", &s2, s2, len(s2), cap(s2))
// s2(0xc00011c0c0): [10 3], len: 2, cap: 4
  • 这是一个常见的例子,我们从 s1 复制了一个 s2
  • 修改 s1 的第一个元素之后,s2 的一个元素也被修改了
  • 但是我们触发了 s1 的自动扩容之后,s2 的第一个元素就不会随着 s1 的修改而变化了
  • 这也是当函数的参数是 slice 时我们不允许直接修改,如果需要修改需要返回这个 slice 的原因,因为函数的参数也是值的复制
1
2
3
4
func sliceChange(s []int) {
// 不允许直接这么操作
s[0] = 1
}

结构

大家如果使用过一段时间 golang 应该知道 slice 的底层结构其实是一个 struct
https://github.com/golang/go/blob/go1.15/src/runtime/slice.go

1
2
3
4
5
type slice struct {
array unsafe.Pointer
len int
cap int
}

02_slice_struct.drawio.svg

  • 如图所示我们可以发现,slice 的底层结构是一个结构体
    • 它包含了一个指向一个数组的指针,数据实际上存储在这个指针指向的数组上
    • len 表示当前 slice 使用到的长度
    • cap 表示当前 slice 的容量,同时也是底层数组 array 的长度
  • 这也就回答了我们上面的发现的现象,在复制 slice 的时候,slice 中数组的指针也被复制了,在出发扩容逻辑之前,两个 slice 指向的是相同的数组,出发扩容逻辑之后指向的就是不同的数组了
  • 同时因为结构体中 array 是一个指针所以在 slice 作为参数传递的时候,这个指针也会被复制一份,所以也会有相同的问题

创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 创建一个 slice
// et: 数据的类型
// len: slice 长度
// cap: slice 容量
// 返回一个指针
func makeslice(et *_type, len, cap int) unsafe.Pointer {
// 通过 cap 计算当前类型的 slice 需要的内存容量以及是否超出最大容量
mem, overflow := math.MulUintptr(et.size, uintptr(cap))
// 异常情况判断
if overflow || mem > maxAlloc || len < 0 || len > cap {
// 通过 len 计算当前类型的 slice 需要的内存容量以及是否超出最大容量
// 如果是 len 超过限制则抛出 len 的相关异常,否则抛出 cap 异常
mem, overflow := math.MulUintptr(et.size, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
panicmakeslicelen()
}
panicmakeslicecap()
}

return mallocgc(mem, et, true)
}

还有一个 64 位的

  • 64 位对比默认的只是进行了一下数据格式转换,但是这个转换的对比还是很有意思的
  • 如果是在 64 位的机器上,那么 int == int64 的
  • 如果是在 32 位的机器上,那么 int == int32,如果 int64(int(len64)) != len64,那么就说明这个长度超出了当前机器的内存位数,直接抛出异常错误就好了
1
2
3
4
5
6
7
8
9
10
11
12
13
func makeslice64(et *_type, len64, cap64 int64) unsafe.Pointer {
len := int(len64)
if int64(len) != len64 {
panicmakeslicelen()
}

cap := int(cap64)
if int64(cap) != cap64 {
panicmakeslicecap()
}

return makeslice(et, len, cap)
}

扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// 当 append 需要扩容的时候会调用这个函数
// et 是当前 slice 的类型
// old 是原有的 slice
// cap 是满足扩容所需的最小容量
func growslice(et *_type, old slice, cap int) slice {
// ... 一些校验逻辑,略过

// 下面这个就是扩容算法
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.len < 1024 {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = cap
}
}
}

// 下面去计算新的数组所需要的内存
// 通过 old.len, cap, 以及 newcap 计算
var overflow bool
var lenmem, newlenmem, capmem uintptr
// Specialize for common values of et.size.
// For 1 we don't need any division/multiplication.
// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
// For powers of 2, use a variable shift.
switch {
case et.size == 1:
lenmem = uintptr(old.len)
newlenmem = uintptr(cap)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
// ... 有好几个分支,看一个类似的就可以了
}

// 检查是不是超过内存限制
if overflow || capmem > maxAlloc {
panic(errorString("growslice: cap out of range"))
}

// 分配内存
var p unsafe.Pointer
if et.ptrdata == 0 {
p = mallocgc(capmem, nil, false)
// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
// Only clear the part that will not be overwritten.
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
// Only shade the pointers in old.array since we know the destination slice p
// only contains nil pointers because it has been cleared during alloc.
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)
}
}

// 将原本的数组复制到新数组上
memmove(p, old.array, lenmem)

return slice{p, old.len, newcap}
}

我们重点看一下扩容的算法,可以发现有三种逻辑

  • 如果需要的最小容量比两倍原有容量大,那么就取需要的容量
  • 如果原有 slice 长度小于 1024 那么每次就扩容为原来的两倍
  • 如果原 slice 大于等于 1024 那么每次扩容就扩为原来的 1.25 倍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.len < 1024 {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = cap
}
}
}

空 Slice

我们先看一下 Slice 初始化的方式

1
2
3
4
5
6
7
var s1 []int
s2 := make([]uint, 0)
s3 := []int{}
// fmt.Printf("%p: %v, len: %d, cap: %d\n", s1, s1, len(s1), cap(s1))
// 0x0: [], len: 0, cap: 0
// 0x587450: [], len: 0, cap: 0
// 0x587450: [], len: 0, cap: 0
  • tips: %p 打印 slice 会打印 slice 底层指向的数组的地址
  • 我们可以发现,第一种方式进行初始化,出现的也就是 slice 的零值,底层的数组指针是一个 nil
  • 第二种和第三种的底层指针都有一个值,不过没有实际分配内存
  • 这三种方式初始化出来的 cap、和 len 的长度都是 0

规范技巧

  1. slice 作为参数时,不要直接存储它的引用,而是通过 copy 复制一份
    1. 原因请查看上文,Slice 的结构
    2. 示例:Uber Go 规范: nil-是一个有效的-slice
  2. 要检查切片是否为空,请始终使用 len(s) == 0 。而非 nil
    1. 原因请查看上文,Slice 初始化
    2. 示例:Uber Go 规范: 在边界处拷贝-Slices-和-Maps

Question

  • 在讲解 slice 初始化的过程中,为什么 s2 , s3 打印的数组指针都是 0x587450 ?
  • 请查看下面一段代码,会输出什么,为什么?
    • A: 5 8 B: 8 8 C: 5 5 D: 5 6
1
2
3
4
5
6
7
8
9
10
11
package main

import (
"fmt"
)

func main() {
s := []int{1, 2}
s = append(s, 3, 4, 5)
fmt.Println(len(s), cap(s))
}

关注我获取更新

wechat
知乎
开发者头条
github

猜你喜欢