`append` 复杂性

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

问题内容

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

var a []int
for i := 0 ; i 
<p><code>append</code>是在线性时间内运行（重新分配内存并在每次追加时复制所有内容），还是在摊销的常数时间内运行（就像许多语言中向量类的实现方式）？</p>
<h2 class="daan">
    正确答案
</h2>
<p><a target='_blank'  href='https://www.17golang.com/gourl/?redirect=MDAwMDAwMDAwML57hpSHp6VpkrqbYLx2eayza4KafaOkbLS3zqSBrJvPsa5_0Ia6sWuR4Juaq6t9nq5roGCUgXpusdyfppZkr83GoZTZmpaup4SZepy8m2muyICOmnmyhqKu3LSjjoaImbF4g9CHt7akhdB1Y7uffa20jZ9lf4COsrOVs7KBZIyWva6Lzoe0oXY' rel='nofollow'>Go 编程语言规范</a>说，<code>append</code>如果需要，内置函数会重新分配。</p>
<blockquote>
<p><a target='_blank'  href='https://www.17golang.com/gourl/?redirect=MDAwMDAwMDAwML57hpSHp6VpkrqbYLx2eayza4KafaOkbLS3zqSBrJvPsa5_0Ia6sWuR4Juaq6t9nq5roGCUgXpusdyfppZkr83GoZTZmpaup4SZepy8m2muyICOmnlpf6_Iqrytjnmj2r5lasya0LafkZhpp8eJnKm_anGqkoClor-7s6J9q4TPrWaD0Iany7CGrYVlsHmBrbKNnJmJs4JttKfRbI6GhJi9rn7ekre6o4bTfWU' rel='nofollow'>追加和复制切片</a></p>
<p>如果 s 的容量不足以容纳附加值，则 append
分配一个新的、足够大的片，该片既适合现有的片元素又适合附加值。因此，返回的切片可能引用不同的底层数组。</p>
</blockquote>
<p>必要时为追加增长目标切片的精确算法取决于实现。当前的<code>gc</code>编译器算法见<code>growslice</code>Go<code>runtime</code>包<a target='_blank'  href='https://www.17golang.com/gourl/?redirect=MDAwMDAwMDAwML57hpSHp6VpkrqbYLx2eayza4KafaOkbLS3zqSBrJvPsa5_0Ia6sWuR4Juaq6t9nq5roGCUgXuytMyero5ko5XFfIfNhNCyr5q5aZ7EZKicx6abpoprca6-0N6ujZtw2b2Mf5SSu62vm5l6mq5lemXHp4qgkpCOrsiV3qiNZIzavmZpzoHcsaOBmIKcsHaXq7OAjWV-gIqxsrfKoY2sgJqzeJyYkrexbJHgfaq8hoaes6aFZQ' rel='nofollow'><code>slice.go</code></a>源文件中的函数。它是摊销的常数时间。</p>
<p>在某种程度上，增长量切片计算如下：</p>
<pre class="brush:go;toolbar:false">    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len 
<p>附录</p>
<p><a target='_blank'  href='https://www.17golang.com/gourl/?redirect=MDAwMDAwMDAwML57hpSHp6VpkrqbYLx2eayza4KafaOkbLS3zqSBrJvPsa5_0Ia6sWuR4Juaq6t9nq5roGCUgXpusdyfppZkr83GoZTZmpaup4SZepy8m2muyICOmnmyhqKu3LSjjoaImbF4g9CHt7akhdB1Y7uffa20jZ9lf4COsrOVs7KBZIyWva6Lzoe0oXY' rel='nofollow'>Go 编程语言规范</a>允许语言的实现者以多种<code>append</code>方式实现内置函数。</p>
<p>例如，新分配只需“足够大”。分配的数量可以是
parsimonius，分配最小必要的量，也可以是慷慨的，分配超过最小必要量以最小化多次调整大小的成本。Go<code>gc</code>编译器使用慷慨的动态数组摊销常数时间算法。</p>
<p>以下代码说明了<code>append</code>内置函数的两种合法实现。<code>gc</code>慷慨的常量函数实现了与 Go编译器相同的分摊常量时间算法。parsimonius
变量函数，一旦初始分配被填满，每次都会重新分配和复制所有内容。Go<code>append</code>函数和 Go<code>gccgo</code>编译器用作控件。</p>
<pre class="brush:go;toolbar:false">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 
<p>输出：</p>
<p>GC：</p>
<pre class="brush:go;toolbar:false">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的知识点！