追加操作的复杂度

Question

在 Go 编程语言中，这个循环的计算复杂度是多少？

var a []int
for i := 0 ; i < n ; i++ {
  a = append(a, i)
}

append 操作的时间复杂度是线性的（每次追加都会重新分配内存并复制所有内容），还是摊销常数时间（类似于许多语言中实现的向量类）？

- Ken Bloom

Answer 1

Go编程语言规范指出，如果需要，append内置函数会重新分配空间。

向切片添加和复制

如果切片s的容量不足以容纳额外的值，则append会分配一个新的、足够大的切片，该切片可以同时容纳现有的切片元素和额外的值。因此，返回的切片可能引用不同的基础数组。

当需要为追加操作增长目标切片时，精确的算法取决于实现。对于当前的gc编译器算法，请参见Go runtime包slice.go源文件中的growslice函数。它是摊销常数时间。

在某种程度上，增长切片的计算量如下：

    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            for newcap < cap {
                newcap += newcap / 4
            }
        }
}

附录

Go编程语言规范允许语言的实现者以多种方式实现append内置函数。

例如，新分配的空间只需“足够大”。分配的数量可以是吝啬的，只分配最少必要的数量，也可以是慷慨的，分配比最少必要的数量更多的空间，以最小化多次调整大小的成本。Go gc编译器使用慷慨的动态数组摊销常数时间算法。

以下代码示例了append内置函数的两个合法实现。慷慨的常数函数实现了与Go gc编译器相同的摊销常数时间算法。吝啬的变量函数，在初始分配填满后，每次都会重新分配和复制所有内容。Go append函数和Go gccgo编译器用作控制。

package main

import "fmt"

// Generous reallocation
func constant(s []int, x ...int) []int {
    if len(s)+len(x) > cap(s) {
        newcap := len(s) + len(x)
        m := cap(s)
        if m+m < newcap {
            m = newcap
        } else {
            for {
                if len(s) < 1024 {
                    m += m
                } else {
                    m += m / 4
                }
                if !(m < newcap) {
                    break
                }
            }
        }
        tmp := make([]int, len(s), m)
        copy(tmp, s)
        s = tmp
    }
    if len(s)+len(x) > cap(s) {
        panic("unreachable")
    }
    return append(s, x...)
}

// Parsimonious reallocation
func variable(s []int, x ...int) []int {
    if len(s)+len(x) > cap(s) {
        tmp := make([]int, len(s), len(s)+len(x))
        copy(tmp, s)
        s = tmp
    }
    if len(s)+len(x) > cap(s) {
        panic("unreachable")
    }
    return append(s, x...)
}

func main() {
    s := []int{0, 1, 2}
    x := []int{3, 4}
    fmt.Println("data    ", len(s), cap(s), s, len(x), cap(x), x)
    a, c, v := s, s, s
    for i := 0; i < 4096; i++ {
        a = append(a, x...)
        c = constant(c, x...)
        v = variable(v, x...)
    }
    fmt.Println("append  ", len(a), cap(a), len(x))
    fmt.Println("constant", len(c), cap(c), len(x))
    fmt.Println("variable", len(v), cap(v), len(x))
}

输出：

gc：

data     3 3 [0 1 2] 2 2 [3 4]
append   8195 9152 2
constant 8195 9152 2
variable 8195 8195 2

gccgo：

data     3 3 [0 1 2] 2 2 [3 4]
append   8195 9152 2
constant 8195 9152 2
variable 8195 8195 2

总之，根据实现方式，一旦初始容量填满，内置函数append在每次调用时可能会或可能不会重新分配内存。

参考资料：

动态数组

摊销分析

追加和复制切片

如果s的容量不足以容纳附加值，append会分配一个新的、足够大的切片，使现有的切片元素和附加的值都适合其中。因此，返回的切片可能指向一个不同的底层数组。

追加到切片规范讨论

规范（在tip和1.0.3处）说明：

“如果s的容量不足以容纳附加值，append会分配一个新的、足够大的切片，使现有的切片元素和附加的值都适合其中。因此，返回的切片可能指向一个不同的底层数组。”

这是否应该是“当且仅当”？例如，如果我知道我的切片的容量足够长，那么我能保证我不会改变底层数组吗？

Rob Pike

是的，你可以确定。

运行时 slice.go 源文件

数组、切片（以及字符串）：'append' 的机制

- peterSO

---

是的，虽然如果语言或库参考可以指定这个的复杂度，那么用户在编写大型应用程序时就可以依赖于这个复杂度，这将是很好的。 - newacct

Answer 2

它不会在每次追加时重新分配内存，这在文档中已经明确说明：

如果 s 的容量不足以容纳额外的值，则 append 会分配一个新的、足够大的切片，该切片既适合现有的切片元素，也适合额外的值。因此，返回的切片可能引用不同的底层数组。

因此，摊销常数时间就是所询问的复杂度。

- zzzz

---

这并不意味着“每次添加时都不会重新分配”。它只是表示必要时会重新分配。 - peterSO

@peterSO：语言作者之一 Rob Pike 持不同意见：https://groups.google.com/d/msg/golang-nuts/o5rFNqd0VjA/HzJHwgl1y6MJ - zzzz

不，他没有。我已经在我的答案中添加了一个附录。 - peterSO

@peterSO：在“是的，你非常有把握”这句话中，哪个词没有清楚地传达Rob对邮件列表OP问题的回答？（问题是：“例如，如果我知道我的切片的容量足够长，那么我是否有把握不会改变底层数组？”）;-) - zzzz

@zzzz，这里的“only”仅适用于现有切片已经足够大的情况。Rob（在引用中）并没有提到当不是这种情况时可能分配多少空间。如果只分配了所需的空间，则不会进行摊销重新分配。 - Dave C