控制 Golang 切片的增长

如果你是Golang 新手，并对它的数组（切片）不太了解，你可能想从这里开始this introduction。

如今，当我们谈论数组时，开发者可能会谈论数组的两种行为之一：一种是静态的（或称为固定数组），另一种是动态的。静态数组的固定长度在定义的时候被初始化完成。动态数组（一般地）用一个静态数组定义，但是当需要的时候，能够增长其长度。那么这是如何实现呢？当你要在动态数组中添加一项条目时，如果数组下面的固定长度已经满了，它会创建一个更大的数组并且将数据拷并到并覆盖更大的数组中。

这种增长和拷贝可能似乎及其地慢，但是动态数组通常使用一种动态分配多余空间的增长算法。这种简单的算法将会增加原来数组的一倍大小。所以当我们试图插入在一个容量为10的数组中插入第11条条目时，我们最终会得到一个新数组容量为20，内容包含11条值。

虽然这有助于避免过度复制，但是它也被严格限制在内存中。想象插入 750 000 条记录到一个数组，一开始它的容量是10。 首先，你必须做18次分配（10， 20， 40， 80 ...）。每一个都不得不被垃圾收集器收集并导致碎片。此外，最终你会得到一个数组，可以容纳 560720 个额外的值（... 327 680, 655 360, 1 310 720）。由于这些原因，只要有可能，最好是初始化动态数组使之有一个合理的尺寸。实际上，你只能估计一个粗略的尺寸，最好是超过一些（它会更少地分配，并最终使用更少的内存）。

数组的大小是固定的，但是由于内置 append 方法，我们获得了动态的行为。事实上 append 会返回一个对象，并强调了这样一个事实，在必要时将会创建。增长算法 append 使用的是存在容量的两倍。

如果我们想要一个不同的行为呢？例如，如果我们想增长一个固定大小的数组呢？或者，如果我们想要在数组中的任意位置上插入一个数值，类似动态的行为呢？在任何位置都可以插入数据的简单的解决方案是重新创建一个新的阵列：

func insert(original []int, position int, value int) []int {  //we'll grow by 1
  target := make([]int, len(original)+1)  //copy everything up to the position
  copy(target, original[:position])  //set the new value at the desired position
  target[position] = value  //copy everything left over
  copy(target[position+1:], original[position:])  return target
}

这当然意味着我们不再获得内存上的性能优势（每一个插入都需要一个新的数组来创建）。要解决这个问题，我们需要了解切片，容量和长度，以及它们与数组的关系。以下代码的输出是什么呢？

x := make([]int, 4)
x = append(x, 5)
fmt.Println(x)

它可以很容易地看上面的代码，并认为我们会写入索引0，从而获得[ 5，0，0，0 ]。但是，上面的代码创建一个基本数组，一个容量为4和一个长度为4的片。当我们append时，我们总是增加切片的长度（如果必要的话，增加数组的容量（通过创建一个新的数组））。上述的结果：[ 0，0，0，0，5 ]。考虑一个更明显的例子：

x := []int{1, 2, 3, 4}
x = append(x, 5)
fmt.Println(x)

我们可以肯定输出是[ 1，2，3，4，5 ]。创建一个“空”的切片，然后预分配指定的长度（数组的长度）和切片的容量的底层数组：

x := make([]int, 0, 4)
x = append(x, 5)
fmt.Println(x)//prints [5]

上述代码中一个有趣的问题是：append返回的是什么？第一种情况：当 len(x) == cap(x)(切片长度等于切片容量)时，将创建一个新的数组，并返回一个新的切片引用。第二种情况：切片长度为0，但容量为4，不会创建一个新的的数组。

（译者注：原文中第二种情况为：In the second case, where len(x) == 4 but cap(x) == 0 是错的。在Go中 len(x) <= cap(x)）

理解了吗？让我们再做个测试，下列代码的输出是什么：

original := []int{1,2,3,4} //a slice with a len and cap of 4
other := original
other[2] = 8
fmt.Println(original)
fmt.Println(other)

other = append(original, 5)
other[2] = 9
fmt.Println(original)
fmt.Println(other)

第一段代码的输出是： [1, 2, 8, 4]。第二段代码的输出是： [1, 2, 8, 4]和[1, 2, 9, 4, 5]。与第一段输出不同，是因为：append操作需要增加底层数组的长度，所以other被指定到一个新的切片上，而original没变。

基于这些认知，我们可以我们自己的基于切片和数组的，有更高控制力的，类似append的插入函数了。我们的函数可以处理两种情况：已达到最大容量(需要增加底层数组长度)、未达到最大容量。首先，我们看看达到最大容量时，如何处理：

func insert(original []int, position int, value int) []int {
    l := len(original)
    var target []int
    if cap(original) == l {
        target = make([]int, l+1, l+10)
        copy(target, original[:position])

        target[position] = value
        copy(target[position+1:], original[position:])
    } else {
        // todo
    }
    return target
}

可以看到，与我们前面实现的简单复制类似。主要区别是：每次长度加10（可以根据你自己的需要调整），而不是增加1。

现在处理第二种情况，未达到最大容量：

    if cap(original) == l {
        //see above
    } else {
        target = append(original, -1)
        copy(target[position+1:], original[position:])
        target[position] = value
    }
    return target
}

上面这段代码的关键是：我们用append追加了一个临时值(-1)到切片。我们知道则不会创建一个新的数组（应为if语句，每次增加10个）。然后，将插入位置右侧的值后移，并最终插入新值。

最后，我们对代码进行重构，使其更紧凑一些：

func insert(original []int, position int, value int) []int {
    l := len(original)
    target := original
    if cap(original) == l {
        target = make([]int, l+1, l+10)
        copy(target, original[:position])
    } else {
        target = append(target, -1)
    }

    copy(target[position+1:], original[position:])
    target[position] = value
    return target
}