go - `append` 复杂度

Question

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

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

append 是按线性时间运行(重新分配内存并在每次附加时复制所有内容)还是按摊销常数时间运行(就像许多语言中向量类的实现方式)？

Answer 1

The Go Programming Language Specification表示 append 内置函数会在必要时重新分配。

Appending to and copying slices

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.

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

部分增长量 slice 计算如下:

    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 Programming Language Specification允许语言的实现者以多种方式实现 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 内置函数可能会或可能不会在每次调用时重新分配。

引用资料:

Dynamic array

Amortized analysis

Appending to and copying slices

If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.

Append to a slice specification discussion

The spec (at tip and 1.0.3) states:

"If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array."

Should this be an "If and only if"? For example, if I know the capacity of my slice is sufficiently long, am I assured that I will not change the underlying array?

Rob Pike

Yes you are so assured.

运行时 slice.go源文件

Arrays, slices (and strings): The mechanics of 'append'