彭诗亮的博客

0%

golang slice 问题排查

发表于

概述

前置知识点

1
2
3
4
5
6
func main()  {
    var a = []int{1,2}
    b := a
    b[1] = 3
    fmt.Println(a)
}
1
[1 3]

先上一段简单代码,修改b[1]的值发现a[1]的值也跟着变化，原因是a和b里成员的地址是指向同一处的

1
2
3
4
5
6
7
var a = []int{1,2}
b := a
b[1] = 3
fmt.Printf("a[0]地址:%p\n", &a[0])
fmt.Printf("a[1]地址:%p\n", &a[1])
fmt.Printf("b[0]地址:%p\n", &b[0])
fmt.Printf("b[1]地址:%p\n", &b[1])
1
2
3
4
a[0]地址:0xc0000b2010
a[1]地址:0xc0000b2018
b[0]地址:0xc0000b2010
b[1]地址:0xc0000b2018

踩坑背景

踩坑经历是发生在刷力扣题组合总和这道题的时候，提交后发现一个case没通过
img_1.png
思考🤔了几遍，没发现出代码逻辑上有什么问题，百思不得其解情况下在本地运行了下该case，发现出现了同样的情况😖
下面是当时刷题提交的代码:(为了方便问题分析，由于力扣原题输出项比较多，因此对该case简化了一下)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func main() {
	res1 := CombinationSum1([]int{7,3,2}, 12)
	fmt.Println(res1)
}

func CombinationSum1(candidates []int, target int) [][]int {
    var res = make([][]int, 0)
    var backtrack func([]int, int, int, []int, int)
    backtrack = func(candidate[]int, begin, size int, ints []int, val int) {
        if val < 0 {
            return
        }
        if val == 0 {
            res = append(res, ints)
        }
        for i := begin; i < size; i++ {
            backtrack(candidate, i, size, append(ints, candidate[i]), val - candidate[i])
        }
    }
    backtrack(candidates, 0, len(candidates), []int{}, target)
    return res
}

查看输出:

1
[[7 3 2] [3 3 3 2] [3 3 2 2 2] [2 2 2 2 2 2]]

很明显[3 3 3 2]加起来不是12，和leetcode出现的问题是一样的

踩坑原因分析

一开始，先是在append处打印下ints变量内容，看看是不是路径和计算有问题

1
2
3
4
if val == 0 {
    fmt.Printf("append ints %v\n", ints)
    res = append(res, ints)
}
1
2
3
4
5
append ints [7 3 2]
append ints [3 3 3 3]
append ints [3 3 2 2 2]
append ints [2 2 2 2 2 2]
[[7 3 2] [3 3 3 2] [3 3 2 2 2] [2 2 2 2 2 2]]

此时，发现了事情的不妙，appendints时ints的成员是正确的，但是最终输出ints的成员确由[3 3 3 3]变为了[3 3 3 2],
于是猜测一定函数backtrack(...append(ints, candidate[i])...)这个函数调用时ints[3]成员的地址的值在后面被修改了，因为通过先前的举例我们也知道了slice里的成员是引用的吗🔍
所以决定断点打印一下来印证自己的猜想，由于断点过程中需要每次查看栈空间函数各个参数的值已经函数递归调用是ints成员的地址值的变化，所以采用gdb工具进行断点

断点追踪

通过上面的输出结果我们知道ints是在第二次append后输出的，所以直接从第二次append后开始分析,并且ints[3]发生了非预期结果，所以只分析ints[3]的地址和值即可

追踪step1

首先，因为发现问题分歧的原因是在res = append(res, ints)这行产生的，因此在这里break一下(如下图所示)
img_11.png

追踪step2

看一下当前栈空间变量成员(如下图所示)
img_12.png

这时，ints[3]还是正常的，打印结果是3,我们记录下当前ints[3]的地址0xc0000ae078,ints变量的地址0xc0000ae060也记录下，后面会用到

追踪step3

当beign=1;i=1时(如下图所示)；candidate[i]会被append到ints中，看下candidate[i] = 3，这时即使ints[3]地址被重新赋值为candidate[i]，也还是会为3，看不出来什么变化，继续走
img_13.png

追踪step4

我们直接跳到i=2;begin=1(如下图所示)；此时发现下面的i=1，证明函数还没开始调用，继续
img_14.png

为什么在i=2后面i又变为了1，并且还有backtrack函数调用？
解释：因为在回溯递归场景中，当前循环里，函数可能还存在其他循环时递归调用的函数，而在其他循环里递归调用的函数成员内存地址是跟当前循环不一样的，所以这里不做追踪

追踪step5

打印candidate[2]，发现值为2(如下图所示),因为这时函数还未调用，candidate[2]还未append，函数将会在下一行调用，所以ints[3]还是3继续追踪
img_15.png

追踪step6

当backtrack函数执行后;candidate[2]被append到了ints中，此时ints[3]的地址的值发生了修改(如下图所示),所以res最后返回结果的切片也发生了修改
img_16.png
此时ints[]3的地址0xc0000ae078还是之前的地址，证实了我们的猜想

追踪step7

接着往下走，因为i=2后，在++为3后不满足i<size判断，所以退出当前循环，进入到下一次循环的函数栈
img_17.png
此时ints[3]地址由0xc0000ae078变为了0xc0000ac058，ints地址由0xc0000ae060变为了0xc0000ac040

之前的ints地址和ints地址在追踪step2记录过

初步结论

在当前函数栈内，ints成员的地址在每次循环调用时是不变的,所以在当前循环函数调用时,ints发生append后，由于是浅拷贝，所以会发生返回切片结果成员数据被污染的情况

追踪结论印证

从前面的结论可知，由于candidate[2]是在循环最后被append的，所以对ints[3]地址指向的值发生了修改，我们可以通过在输入项中增加一个元素，来印证当前结论

1
res1 := CombinationSum1([]int{7,3,2, 8}, 12)

打印输出结果

1
2
3
4
5
6
append ints [7 3 2]
append ints [3 3 3 3]
append ints [3 3 2 2 2]
append ints [2 2 2 2 2 2]
append ints [2 2 8]
[[7 3 2] [3 3 3 8] [3 3 2 2 2] [2 2 2 2 2 8] [2 2 8]]

可以看到[3 3 3 2]变为了[3 3 3 8]

How To Fix

了解问题根本原因后想解决就很简单了，我们只要在append时深拷贝一次ints就可以了
解决后完整代码:

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
func main() {
	res1 := CombinationSum2([]int{7,3,2, 8}, 12)
	fmt.Println(res1)
}

func CombinationSum1(candidates []int, target int) [][]int {
	var res = make([][]int, 0)
	var backtrack func([]int, int, int, []int, int)
	backtrack = func(candidate[]int, begin, size int, ints []int, val int) {
		if val < 0 {
			return
		}
		if val == 0 {
			var tmp = make([]int, len(ints))
			copy(tmp, ints)
			fmt.Println("append after copied ints", tmp)
			res = append(res, tmp)
		}
		for i := begin; i < size; i++ {
			backtrack(candidate, i, size, append(ints, candidate[i]), val - candidate[i])
		}
	}
	backtrack(candidates, 0, len(candidates), []int{}, target)
	return res
}

输出:

1
2
3
4
5
6
append after copied ints [7 3 2]
append after copied ints [3 3 3 3]
append after copied ints [3 3 2 2 2]
append after copied ints [2 2 2 2 2 2]
append after copied ints [2 2 8]
[[7 3 2] [3 3 3 3] [3 3 2 2 2] [2 2 2 2 2 2] [2 2 8]]

算法提交通过👏
img_18.png