`append`复杂度

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

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

是否append线性时间操作（重新分配内存和复制在每个附加的所有内容），或在分期常量时间（喜欢的方式在许多语言矢量类implemnted）？

来源

2013-03-29 Ken Bloom

The Go Programming Language Specification说，append内置函数，如果有必要重新分配。

Appending to and copying slices

如果s的容量不够大，以适应更多的价值，追加分配一个新的，足够大的切片适合两个现有切片元素和附加价值。因此，返回的切片可能指代不同的基础阵列。

在必要时增加目标切片的精确算法对于追加是依赖于实现的。有关当前的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 Programming Language Specification允许语言的实现者实现多种方式的append内置功能。

例如，新的分配只需要“足够大”。分配的金额可能是parsimonius，分配最低必要金额或慷慨，分配超过最低必要金额以最小化多次调整大小的成本。 Go gc编译器使用慷慨的动态数组分摊恒定时间算法。

以下代码说明了append内置函数的两个合法实现。慷慨的常量函数实现与编译器相同的分摊恒定时间算法。一旦初始分配被填充，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内置in函数可能会或可能不会在每次调用时重新分配。

参考文献：

Dynamic array

Amortized analysis

Appending to and copying slices

如果s的容量不够大，以适应更多的价值， append分配一个新的，足够大的切片适合现有sl的冰元素和附加值。因此，返回的切片可能指代不同的基础阵列。

Append to a slice specification discussion

该规范（在塞尖和1.0.3）规定：

“如果s的容量不够大，以适应附加的值，append分配一个新的，足够大的片这适合现有切片元素和附加值。因此，返回的切片可能引用不同的基础数组。

这应该是“如果且仅当”？例如，如果我知道我的片的容量足够长，我确信我会不更改底层数组？

Rob Pike

是的，你是如此放心。