Slice Append Trap in Golang

发表于 | 分类于

最近再用没事的时间刷leetcode，顺便学习一下Golang的简单语法，然后就被坑了。。。

今天遇到的题目是 #46-Permutations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

题目应该来说比较常规啦，没什么算法可言，输出就是 n! 了，就拿笨办法做吧，于是就有了下面我的code，非常无脑的反复堆叠数组

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 permute(nums []int) [][]int {
    var ret,hold [][]int
    for _,v := range nums {
        hold = append(hold, []int{v})
    }
    for i := 1; i < len(nums); i++ {
        for _,arr := range hold {
            for _,v := range nums {
                flag := true
                for _,a := range arr {
                    if a == v {
                        flag = false
                        break
                    }
                }
                if flag {
                    ret = append(ret, append(arr,v))
                }
            }
        }
        hold = ret
        ret = make([][]int, 0)
    }
    return hold
}

本来以为是辣么简单的逻辑，然而。。。竟然出现了wrong answer…

你可以说我run time error，你可以说我time limit，但是为什么会有wrong answer…

1
2
3
4
5
6
Input:
[6,3,2,7,4,-1]
Output:
[[6,3,2,-1,7,4],[6,3,2,-1,4,7],[6,3,2,-1,7,4],[6,3,2,-1,4,7],...
Expected:
[[6,3,2,7,4,-1],[6,3,2,7,-1,4],[6,3,2,4,7,-1],[6,3,2,4,-1,7],...

看起来好像是顺序问题，但仔细一看Output的前两个元素一毛一样啊 ヽ(*。>Д<)o゜

吐了好几摊血之后，有了下面一段debug记录

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
func permute(nums []int) [][]int {
    var ret,hold [][]int
    for _,v := range nums {
        hold = append(hold, []int{v})
    }
    for i := 1; i < len(nums); i++ {
        for _,arr := range hold {
            for _,v := range nums {
                fmt.Println(1,ret) // #1
                flag := true
                for _,a := range arr {
                    if a == v {
                        flag = false
                        break
                    }
                }
                if flag {
                    fmt.Println(2,ret) // #2
                    a := append(arr,v)
                    fmt.Println(3,ret) // #3
                    ret = append(ret, a)
                    fmt.Println(4,ret) // #4
                }
            }
        }
        hold = ret
        ret = make([][]int, 0)
    }
    return hold
}

// Output 节选，前面的都对，不要问为什么
1 []
1 []
1 []
1 []
2 []
3 []
4 [[1 2 3 4]]
1 [[1 2 3 4]]
2 [[1 2 3 4]]
3 [[1 2 3 5]]  // <-
4 [[1 2 3 5] [1 2 3 5]]

作为一个相信科学的小码农，我第一次感到了来自未知世界的恶意，#2 和 #3 之间的操作可以说与数组ret完全没有关系，然而，ret的值，变了。。。 没错，当len(arr)=2的时候没有变，当len(arr)=4的时候没有变，而在len(arr)=3的时候，变了。

本着Geek精神，又加了点料，打印了ret和中间量a的地址

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
func permute(nums []int) [][]int {
    var ret,hold [][]int
    for _,v := range nums {
        hold = append(hold, []int{v})
    }
    for i := 1; i < len(nums); i++ {
        for _,arr := range hold {
            for _,v := range nums {
                fmt.Printf("%p ",ret)
                fmt.Println(1,ret)
                flag := true
                for _,a := range arr {
                    if a == v {
                        flag = false
                        break
                    }
                }
                if flag {
                    fmt.Printf("%p ",ret)
                    fmt.Println(2,ret)
                    a := append(arr,v)
                    fmt.Printf("%p %p ",ret, a)
                    fmt.Println(3,ret)

                    ret = append(ret, a)
                    fmt.Printf("%p %p ",ret, a)
                    fmt.Println(4,ret)
                }
            }
        }
        hold = ret
        ret = make([][]int, 0)
    }
    return hold
}
// Output - 没有错误的地方
0x1953e4 1 []
0x1953e4 2 []
0x1953e4 0x10415ae0 3 []
0x10462220 0x10415ae0 4 [[1 2 3]]
0x10462220 1 [[1 2 3]]
0x10462220 2 [[1 2 3]]
0x10462220 0x10415b20 3 [[1 2 3]]
0x10448280 0x10415b20 4 [[1 2 3] [1 2 4]]
// Output - 出错的地方
0x1953e4 1 []
0x1953e4 2 []
0x1953e4 0x10415ae0 3 []
0x104a3610 0x10415ae0 4 [[1 2 3 4]] // <-前一个循环
0x104a3610 1 [[1 2 3 4]]
0x104a3610 2 [[1 2 3 4]]
0x104a3610 0x10415ae0 3 [[1 2 3 5]] // <-后一个循环
0x104482a0 0x10415ae0 4 [[1 2 3 5] [1 2 3 5]]

在没有出错的地方，每一次临时变量a的地址都是会变动的，而在出错的地方，第二次声明临时量a的时候地址没有发生变化，很显然ret还在引用着这个地址，于是后一次的更新直接导致ret的改变。简直就像是恐怖片。。。

网上查了一些资料（见reference吧），Golang的slice有自己的优化方式。而从我们遇到的问题来解释，事实上呢，0x10415ae0——这个地址就是此时arr的地址，不用说此时arr的cap肯定还有富余，底层在执行append的时候就偷懒没有去申请新的地址，于是就悲剧了

关于slice的cap是怎么分配的，做了一个试验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var a []int
for i:=0;i<100;i++ {
    a = append(a,1)
    fmt.Println(cap(a),a)
}
// Output
2 [1]
2 [1 1]
4 [1 1 1]
4 [1 1 1 1]
8 [1 1 1 1 1]
8 [1 1 1 1 1 1]
8 [1 1 1 1 1 1 1]
8 [1 1 1 1 1 1 1 1]
16 [1 1 1 1 1 1 1 1 1]
16 [1 1 1 1 1 1 1 1 1 1]
16 [1 1 1 1 1 1 1 1 1 1 1]

结论应该显而易见了，而对于怎么修正 #46-Permutations 的solution，在此也就不赘述了


Reference
  1. leetcode: https://leetcode.com/
  2. Golang：slice之append时原数组发生变化的问题:
    https://blog.csdn.net/books1958/article/details/46931127
  3. 对GoLang里的slice要谨慎使用append操作:
    https://blog.csdn.net/gzliudan/article/details/23515381

人到中年，整个一部西游记！悟空的压力，八戒的身材，老沙的发型，唐僧一样絮絮叨叨！还特么的离西天越来越近了[捂脸]