一个关于切片的小问题

偶然在网上瞧见了一道 Go 语言的面试题,本以为不难,但却没答对,所以藉此再来回顾下关于 Go 语言 Slice 的知识。

关于切片的小问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main

import (
"fmt"
)

func main() {
s := []int{1, 2, 3}
ss := s[1:]
ss = append(ss, 4)

for _, v := range ss {
v += 10
}

for i := range ss {
ss[i] += 10
}

fmt.Println(s)
}

看似不难,但是能否正确写出答案,考验的还是自己对切片的底层知识是否掌握的够好。

切片的知识回顾

切片(Slice),它的内部一般会维护三个变量,ptr(pointer)、len(length)、cap(capacity)。在初学切片时,我们知道在对数组或者切片进一步进行切片后,新生成的子切片是原有数组或切片的视图(View)。
也就是说,我们对子切片进行任何的修改,都会作用在他的底层数组上。但是如果仅仅浅显的认识到这一点还是不够的,稍有疏忽就会出错。

所以,这道题一不留神就很容易得出 [1 12 13] 这种错误答案。接下来分块来分析一下

问题分析

1
2
3
s := []int{1, 2, 3}
ss := s[1:]
ss = append(ss, 4)

首先第一个问题:上面每一行产生的变量,它的值、lencap 分别是多少?

第一行中,s 是一个原始切片,这种原始切片的 lencap 的大小都是一样的,因此可以很容易的知道,此时 slencap 都是 3。

第二行中的 ss 则是 s 的子切片,其值为 [2 3],可见 len 应该为 2,那么它的 cap 应该是多少?首先应该明白一点,切片可以向后扩展,但是不可以向前扩展。因为 ss 是截取 s 最后两个值,据此我们可以判断出 sscap 应该为 2。倘若有另一个变量 ss2 := s[:2],值为 [1 2],根据可以向后扩展的原则,ss2 的底层数组 s 中还有一个元素的位置,所以此时 ss2cap 的值就应该为 3。

第三行,涉及到 append 函数的知识。在第二行的分析中,了解到此时 sslen 已经等于 cap 了,换句话是已经满了。如果非要在子切片上继续添加新元素就已经超过底层数组的 cap 了,那么 append 函数又是如何处理这个问题的呢?

1
2
3
4
5
6
7
8
9
10
// The append built-in function appends elements to the end of a slice. If
// it has sufficient capacity, the destination is resliced to accommodate the
// new elements. If it does not, a new underlying array will be allocated.
// Append returns the updated slice. It is therefore necessary to store the
// result of append, often in the variable holding the slice itself:
// slice = append(slice, elem1, elem2)
// slice = append(slice, anotherSlice...)
// As a special case, it is legal to append a string to a byte slice, like this:
// slice = append([]byte("hello "), "world"...)
func append(slice []Type, elems ...Type) []Type

根据 append 函数的描述,如果容量足够,那么会 reslice 来容纳新的元素,倘若容量不够的话,就会重新分配一个新的底层数组,这也是为什么 append 函数会要求接收返回值,因为 append 函数有可能导致底层素组的变化。

回到刚才的分析,现在已经明白,新产生的 ss 已经不是原来的 ss 了,底层数组也不是 s ,具体是那个底层数组也只有系统才知道。因此后续代码再对 ss 进行何种操作,都不会再作用到 s,所以我们问题的最终答案就是 s 没有变化,结果仍为 [1 2 3]

不过,我们还需要再次思考,通过重新分配底层数组而产生的切片,它的 cap 应该为多少呢?通过查看源码,可以在 src/runtime/slice.go 中找到一个名为 growslice 的函数,可以略窥一二。

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
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
}
}
}

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)
case et.size == sys.PtrSize:
lenmem = uintptr(old.len) * sys.PtrSize
newlenmem = uintptr(cap) * sys.PtrSize
capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
newcap = int(capmem / sys.PtrSize)
case isPowerOfTwo(et.size):
var shift uintptr
if sys.PtrSize == 8 {
// Mask shift for better code generation.
shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
} else {
shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
}
lenmem = uintptr(old.len) << shift
newlenmem = uintptr(cap) << shift
capmem = roundupsize(uintptr(newcap) << shift)
overflow = uintptr(newcap) > (maxAlloc >> shift)
newcap = int(capmem >> shift)
default:
lenmem = uintptr(old.len) * et.size
newlenmem = uintptr(cap) * et.size
capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
capmem = roundupsize(capmem)
newcap = int(capmem / et.size)
}

// 省略部分代码

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

通过阅读上面的代码,可以发现,对于一个切片的扩容有以下规则

  • 如果指定扩容大小大于旧切片容量的两倍,那么新切片的容量就为指定容量大小
  • 如果指定扩容大小小于旧切片容量的两倍
    • 当旧切片长度小于 1024 时,新切片的容量则为旧容量的两倍
    • 若就切片长度大于 1024 时,新切片的容量会在旧容量的基础上每次递增 1/4,注意这里是每次增加后的 1/4 并且前提是不超过指定容量值。
      如果因为增加导致新容量的值溢出,则新容量就会直接为指定容量值
  • (后面还基于切片的类型对切片容量做出了一些调整,但是我似乎没看懂啊(雾)

所以,对于重新指定了新的底层数组的 ss在原来容量大小为 2 的基础上,新的容量大小应该为旧容量的两倍,也就是 4

后面还有两处循环,对于第一处循环

1
2
3
for _, v := range ss {
v += 10
}

因为 Go 语言都是值传递,且此处只是对取得值进行修改,而非在原来的地址对值进行修改,因此很显然此循环不会对任何切片内的值做出改变。

至于第二处循环

1
2
3
for i := range ss {
ss[i] += 10
}

就是在 ss 上对每个元素加 10,因此,ss 的内容应该为 [12 13 14]

正确答案

综上所述,这个关于切片的小问题,最终的输出结果应该为 [1 2 3]

文章作者: Inno Fang
文章链接: https://innofang.github.io/2020/02/28/一个关于切片的小问题/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来自 Inno's Blog