golang slice 一个易错点,今天我被卡了一个多小时 - V2EX
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 4977 次点击
    这是一个创建于 2607 天前的主题,其中的信息可能已经有所发展或是发生改变。

    今天刷 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     Solana     2617 人在线   最高记录 6679       Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 25ms UTC 03:11 PVG 11:11 LAX 19:11 JFK 22:11
    Do have faith in what you're doing.
    ubao msn snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86