`append` 复杂性

偷偷努力，悄无声息地变强，然后惊艳所有人！哈哈，小伙伴们又来学习啦~今天我将给大家介绍《`append` 复杂性》，这篇文章主要会讲到golang等等知识点，不知道大家对其都有多少了解，下面我们就一起来看一吧！当然，非常希望大家能多多评论，给出合理的建议，我们一起学习，一起进步！

问题内容

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

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

    正确答案

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

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

必要时为追加增长目标切片的精确算法取决于实现。当前的gc编译器算法见growsliceGoruntime包slice.go源文件中的函数。它是摊销的常数时间。
在某种程度上，增长量切片计算如下：
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len 
附录
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  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 
输出：
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分配一个新的、足够大的片来适应现有的片元素和附加值。因此，返回的切片可能引用不同的底层数组。
[附加到切片规范讨论](https://groups.google.com/d/topic/golang-
nuts/o5rFNqd0VjA/discussion)
规范（在提示和 1.0.3 中）指出：
“如果 s
的容量不足以容纳附加值，则append分配一个新的、足够大的切片，该切片既适合现有切片元素又适合附加值。因此，返回的切片可能引用不同的底层数组。”
这应该是“当且仅当”吗？例如，如果我知道我的 slice 的容量足够长，我能保证不会更改底层数组吗？
[罗布·派克](https://groups.google.com/d/msg/golang-
nuts/o5rFNqd0VjA/HzJHwgl1y6MJ)
是的，你很放心。

运行时slice.go源文件
数组、切片（和字符串）：“追加”的机制
到这里，我们也就讲完了《`append` 复杂性》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于golang的知识点！