12

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

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

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

4

2 回答 2

22

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

追加和复制切片

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

必要时，为追加增长目标切片的精确算法取决于实现。当前的gc编译器算法见growsliceGoruntime包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
            }
        }
}

附录

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

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

以下代码说明了append内置函数的两种合法实现。gc慷慨的常量函数实现了与 Go编译器相同的分摊常量时间算法。parsimonius 变量函数，一旦初始分配被填满，每次都会重新分配和复制所有内容。Goappend函数和 Gogccgo编译器用作控件。

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分配一个新的、足够大的片，该片既适合现有的片元素又适合附加值。因此，返回的切片可能引用不同的底层数组。

附加到切片规范讨论

规范（在提示和 1.0.3 中）指出：

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

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

罗布·派克

是的，你很放心。

运行时slice.go源文件

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

于 2013-03-29T12:39:49.657 回答
-1

它不会在每个追加时重新分配，并且在文档中非常明确地说明：

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

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

于 2013-03-29T11:44:03.927 回答