V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
The Go Programming Language
http://golang.org/
Go Playground
Go Projects
Revel Web Framework
EchoUtopia
V2EX  ›  Go 编程语言

golang slice 一个易错点,今天我被卡了一个多小时

  •  
  •   EchoUtopia · 2018-10-10 22:14:38 +08:00 · 4521 次点击
    这是一个创建于 2233 天前的主题,其中的信息可能已经有所发展或是发生改变。

    今天刷 leetcode 解决一个获取二叉树深度算法题的时候我对我的解法正确性很确定,但是结果就是不对,因为刚接触 leetcode,二叉树输入都是数组形式给出的,我不知道怎么构造出树来,不知道怎么调试,所以这个问题卡了我半天,真的不知所措。后面我用同样的 python 解法都没问题,肉眼排查了半天才找到疑点。于是自己写了下面的 demo,才知道问题出在哪。

    那么问题来了,不执行以下代码代码你脑解出答案么?

    demo:

    package main
    
    import "fmt"
    
    func main() {
        a := []int{1}
        b := a
        a = a[:0]
        a = append(a, 2)
        a = append(a, 3)
        fmt.Println(a, b)
    }
    

    其实这个问题专门拿出来说可能比较容易避开这个坑,但是实际情况可能很容易被忽视掉。

    有问题版本:

    func maxDepth(root *TreeNode) int {
        if root == nil{
            return 0
        }
        depth := 0
        stack := []*TreeNode{root}
        for ;len(stack) != 0;{
            depth ++
            c := stack
            stack = stack[:0]
            for _, v := range c{
                if v.Left != nil{
                    stack = append(stack, v.Left)
                }
                if v.Right != nil{
                    stack = append(stack, v.Right)
                }
            }
        }
        return depth
    }
    

    正确版本:

    func maxDepth(root *TreeNode) int {
        if root == nil{
            return 0
        }
        depth := 0
        stack := []*TreeNode{root}
        for ;len(stack) != 0;{
            depth ++
            nxtSt := make([]*TreeNode, 0)
            for _, v := range stack{
                if v.Left != nil{
                    nxtSt = append(nxtSt, v.Left)
                }
                if v.Right != nil{
                    nxtSt = append(nxtSt, v.Right)
                }
            }
            stack = nxtSt
        }
        return depth
    }
    

    希望能帮到同样是 golang 新手的你^_^

    11 条回复    2018-10-11 11:49:24 +08:00
    zjlletian
        1
    zjlletian  
       2018-10-11 00:46:03 +08:00
    的确受教了,golang 的 slice 在内存中不光是连续的数据,而且是有保存长度的,append 到 a,但 b 的长度还是 1
    Mitt
        2
    Mitt  
       2018-10-11 00:48:48 +08:00 via iPhone
    应该是切片后虽然 len 为 0 但地址一样且有足够空间导致的吧
    oovveeaarr
        3
    oovveeaarr  
       2018-10-11 00:58:41 +08:00
    https://golang.org/pkg/builtin/#append

    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:
    巴拉巴拉,append 会返回更新过的 slice。所以有必要存储 append 返回的结果,通常我们会使用之前保存这个 slice 的变量本身来保存。

    的确算是半个坑吧,不过我个人的话可能 LZ 不说可能没什么机会遇到。
    我个人是想 append 都有要求重新赋值操作了,就潜意识认为肯定返回的内容和之前的内容不一样,就不会做这种骚操作了。
    honestyccc
        4
    honestyccc  
       2018-10-11 01:20:10 +08:00
    a 在第二次 append 时候由于切片容量不够了,所以 append 实际是返回一个新的切片
    donething
        5
    donething  
       2018-10-11 02:04:58 +08:00 via Android   ❤️ 1
    这个问题,《 Go 实战》里讲过很清楚。切片后仍然共享内存,只有在 append()后容量不足,才会重新开辟内存。所以切片时指定容量非常重要,如 a=a[0:0:0]
    crayontxx
        6
    crayontxx  
       2018-10-11 07:33:07 +08:00
    这个 Go Blog 上说过
    https://blog.golang.org/go-slices-usage-and-internals
    简单的说需要把 slice 看成这样的一个 struct
    {
    data *T
    cap, len int
    }
    上面的其他文章也是值得看的
    EchoUtopia
        7
    EchoUtopia  
    OP
       2018-10-11 09:33:50 +08:00
    @donething @Mitt @oovveeaarr @honestyccc @crayontxx 主要以前用 python 经常这样用,所以这个问题被我给忽视掉了,所以总结起来就是拷贝 slice 最好用 copy 函数, 否则要谨慎,因为如果没扩容就会两个 slice 都会被影响
    zarte
        8
    zarte  
       2018-10-11 11:21:39 +08:00
    还是觉得像其他语言那样比较好,默认创建新变量,要引用的时候手动赋值地址。
    EchoUtopia
        9
    EchoUtopia  
    OP
       2018-10-11 11:29:13 +08:00
    @zarte #8 如果你用数组,而不是 slice,那就跟你说的一样了
    xrlin
        10
    xrlin  
       2018-10-11 11:48:12 +08:00
    其实就是底层实现的内存分配问题,一开始我也有点懵,后来了解了实现后还是挺好理解的,反正需要修改到值的时候要慎重,当时还专门写了笔记记录 slice 和数组各种可能遇到的问题
    https://xrlin.github.io/Golang%E4%B8%AD%E7%9A%84%E6%95%B0%E7%BB%84%E4%B8%8ESlice/
    icexin
        11
    icexin  
       2018-10-11 11:49:24 +08:00
    go 里面的 slice 是一个 descriptor 结构,包含 ptr, len, cap 三个字段,切片只是修改 len 和 cap,时间复杂度为 O(1)。
    python 的 slice 是一次新建一个数组再拷贝的操作,时间复杂度为 O(n)。两者设计理念不一样。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3316 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 11:59 · PVG 19:59 · LAX 03:59 · JFK 06:59
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.