追加复杂度

Question

Go编程语言中此循环的计算复杂度是多少？

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

并append以线性时间（重新分配内存和每个追加拷贝的一切），或在固定的时间里操作（比如在许多语言方式矢量类是implemnted）？

Answer 1

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

附加并复制切片

如果s的容量不足以容纳附加值，则append分配一个新的，足够大的切片，使其既适合现有slice元素又适合附加值。因此，返回的切片可以引用不同的基础数组。

必要时，增加目标切片的精确算法取决于实现。有关当前的gc编译器算法，请参见growsliceGo
runtime包slice.go源文件中的函数。固定时间摊销。

增长量切片计算部分读取：

    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
            }
        }
}

附录

在围棋编程语言规范允许语言的实现者来实现append的内置功能在许多方面。

例如，新的分配仅必须“足够大”。分配的数量可以是parsimonius（分配最小的必要数量），或者是慷慨的，分配的数量大于最小必需的数量，以使多次调整大小的成本最小化。Go
gc编译器使用大量的动态数组摊销恒定时间算法。

以下代码说明了append内置函数的两种合法实现。慷慨的常量函数实现了与Go
gc编译器相同的摊销常量时间算法。一旦完成了初始分配，parsimonius变量函数便会重新分配并复制所有内容。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分配一个新的足够大的切片，使其既适合现有slice元素又适合附加值。因此，返回的切片可以引用不同的基础数组。

附加到切片规范讨论

规范（技巧和1.0.3）指出：

“如果s的容量不足以容纳其他值，则append分配一个新的，足够大的切片，使其既适合现有slice元素又适合附加值。因此，返回的切片可能引用了另一个基础数组。”

这应该是“如果且仅当”吗？例如，如果我知道切片的容量足够长，是否可以确定不会更改基础数组？

罗伯·派克

是的，你很放心。

运行时slice.go源文件

数组，切片（和字符串）：“追加”的机制