技术

Go语言slice前置插入（prepend）的坑

Go语言

最近在工作中遇到一个需求，抽象为数据结构的问题就是：对于一个只记录了前向节点的链表，把其中所有节点的值转化为一个数组，数组需要保持原链表中各个值的顺序。也就是一个链表节点的数据结构长这样：

1
2
3
4
type ListNode struct {
    Val int
    Prev *ListNode
}

需要向前遍历这个链表，用一个slice记录其每个节点的值，并且保持值在链表中的相对位置。咋一看这个需求很简单，只需要向前遍历链表，然后不断地往slice的最前面插入链表节点的值就行。于是写出了这样的代码：

1
2
3
4
5
6
7
var res []int
currNode := head // Type of head is *ListNode
for head != nil {
    // Prepend
    res = append([]int{head.Val}, res...)
    currNode = currNode.Prev
}

相信很多人都会这么写，这样写也没有逻辑上的问题，并且很多算法题的题解都是这么写的。还有一些博主将这样的前置插入美名曰prepend，写一些博客教导新手这么写。
先开始我也是这么写的（主要还是因为前人的代码里存在类似的操作），于是写几个ut过了之后，找别人review，reviewer也觉得可以，于是代码就心安理得地提交了。
等到代码部署的时候，突然发现latency暴增，于是紧急回滚代码看问题。最终高latency的来源锁定在上面的代码，想了一下，高latency只可能来源于prepend操作（关于append的原理，可以看我之前的一篇博客：Go的奇特之处2–Go语言的slice）。在这种prepend操作中，每次append都会申请新地址空间，这是非常耗时的，如果链表长度很长（在这个需求中链表的长度可以达到上千），那么若干次申请新地址空间，就会造成高latency。
找到原因，便开始着手该代码，由于这个需求能知道链表的最大可能长度，改起来比较简单：从一开始为slice申请足够的空间，然后将数值从后向前填入到slice中，最后截取slice即可：

1
2
3
4
5
6
7
8
9
10
// length is the longest possible length of list.
res := make([]int, length)
iter := length-1
currNode := head // Type of head is *ListNode
for head != nil {
    res[iter] = head.Val
    head = head.Prev
    iter--
}
res = res[iter+1:]

如果实现无法知道链表的最大可能长度，可以先设置一个较大值，每次填充slice前先检查一下iter是否大于等于0，如果不是则对slice进行扩容再操作。
修改完代码，和之前的方法进行本地测试对比，发现latency竟然能够下降两个数量级（latency单位为毫秒）。不得不感叹申请新地址空间是一个多么耗时的操作，以后写代码需要多多注意。

分享到