Go中使用append前置的机制是什么？

Question

假设我有一个类型 int 的切片 slice。在声明时，我将第三个参数设置为 size，我相信通过设置切片的 cap 参数，它至少为 size 整数保留内存。

slice:=make([]int,0,size)

现在，假设我有一个整型变量 value。要将它添加到末尾的切片中，我使用

slice=append(slice,value)

如果当前切片中的元素数量少于size，则无需将整个底层数组复制到新位置即可添加新元素。

此外，如果我想按照 here and 的建议将 value 添加到 slice 之前，我使用

slice=append([]int{value},slice...)

我的问题是，在这种情况下会发生什么？如果元素个数还是小于size，元素是怎么存入内存的？假设在调用 make() 函数时进行连续分配，是否所有现有元素都右移以释放第一个 space 的值？还是重新分配内存并复制所有元素？

询问的原因是我希望我的程序尽可能快，并且想知道这是否是导致速度变慢的可能原因。如果是这样，是否有任何其他方法可以更省时？

Answer 1

"prepend" 调用需要分配一个数组并复制所有元素，因为 Go 中的切片被定义为起点、大小和分配（分配从起点开始计算） .

切片无法知道第一个元素之前的元素可用于扩展切片。

会发生什么

slice = append([]int{value}, slice...)

是

分配了单个元素的新数组value（可能在堆栈上）
创建一个切片来映射这个元素（start=0，size=1，alloc=1）
append 调用完成
append 发现没有足够的空间来扩展 single-element 切片，因此分配一个新数组并复制所有元素
创建一个新的切片对象来引用这个数组

如果大型容器两端的 appending/removing 是您应用程序的常见用例，那么您需要一个 deque 容器。不幸的是，它在 Go 中不可用，并且不可能在保持可用性的同时高效地编写泛型包含类型（因为 Go 仍然缺乏泛型）。

然而，您可以为您的特定情况实现一个双端队列，这很容易（例如，如果您有一个已知上限的大容器，可能 circular buffer 就是您所需要的，这只是一个几行代码）。

我是 Go 的新手，所以以下可能是非常糟糕的 Go 代码...但它是尝试使用不断增长的循环缓冲区实现双端队列（取决于用例，这可能是也可能是不是一个好的解决方案）

type Deque struct {
    buffer  []interface{}
    f, b, n int
}

func (d *Deque) resize() {
    new_buffer := make([]interface{}, 2*(1+d.n))
    j := d.f
    for i := 0; i < d.n; i++ {
        new_buffer[i] = d.buffer[j]
        d.buffer[j] = nil
        j++
        if j == len(d.buffer) {
            j = 0
        }
    }
    d.f = 0
    d.b = d.n
    d.buffer = new_buffer
}

func (d *Deque) push_back(x interface{}) {
    if d.n == len(d.buffer) {
        d.resize()
    }
    d.buffer[d.b] = x
    d.b++
    if d.b == len(d.buffer) {
        d.b = 0
    }
    d.n++
}

func (d *Deque) push_front(x interface{}) {
    if d.n == len(d.buffer) {
        d.resize()
    }
    if d.f == 0 {
        d.f = len(d.buffer)
    }
    d.f--
    d.buffer[d.f] = x
    d.n++
}

func (d *Deque) pop_back() interface{} {
    if d.n == 0 {
        panic("Cannot pop from an empty deque")
    }
    if d.b == 0 {
        d.b = len(d.buffer)
    }
    d.b--
    x := d.buffer[d.b]
    d.buffer[d.b] = nil
    d.n--
    return x
}

func (d *Deque) pop_front() interface{} {
    if d.n == 0 {
        panic("Cannot pop from an empty deque")
    }
    x := d.buffer[d.f]
    d.buffer[d.f] = nil
    d.f++
    if d.f == len(d.buffer) {
        d.f = 0
    }
    d.n--
    return x
}

Answer 2

重新切片和复制

内置 append() 总是将元素附加到切片。您不能（单独）使用它来添加元素。

话虽如此，如果你有一个大于长度的切片容量（在其元素之后有 "free" space）你想在前面添加一个元素，你可以重新切片原始切片，将所有元素复制到更高的索引以为新元素腾出空间，然后将元素设置为第 0^th 索引。这将不需要新的分配。这就是它的样子：

func prepend(dest []int, value int) []int {
    if cap(dest) > len(dest) {
        dest = dest[:len(dest)+1]
        copy(dest[1:], dest)
        dest[0] = value
        return dest
    }

    // No room, new slice need to be allocated:
    // Use some extra space for future:
    res := make([]int, len(dest)+1, len(dest)+5)
    res[0] = value
    copy(res[1:], dest)
    return res
}

正在测试：

s := make([]int, 0, 5)
s = append(s, 1, 2, 3, 4)
fmt.Println(s)
s = prepend(s, 9)
fmt.Println(s)
s = prepend(s, 8)
fmt.Println(s)

输出（在 Go Playground 上尝试）：

[1 2 3 4]
[9 1 2 3 4]
[8 9 1 2 3 4]

注意：如果没有空间容纳新元素，因为性能现在很重要，我们不只是这样做：

res := append([]int{value}, dest...)

因为它进行了比需要更多的分配和复制：为文字 ([]int{value}) 分配一个切片，然后 append() 在向其附加 dest 时分配一个新切片。

相反，我们的解决方案只分配一个新数组（通过 make()，甚至为将来的增长保留一些 space），然后只需将 value 设置为第一个元素并复制 dest（前面的元素）。

有链表

如果您需要多次前置，普通切片可能不是正确的选择。一种更快的替代方法是使用链表，在链表之前添加一个元素不需要分配切片/数组和复制，您只需创建一个新节点元素，然后通过将其指向旧根来将其指定为根（第一个元素）。

标准库在 container/list 包中提供了通用实现。

手动管理更大的后备阵列

坚持使用普通切片和数组，还有另一种解决方案。

如果您愿意自己管理更大的后备阵列（或切片），可以通过在您使用的切片之前留下空闲 space 来实现。前置时，您可以从后备更大的数组或切片创建一个新的切片值，它从一个索引开始，为 1 个要前置的元素留出空间。

不完整，仅供演示：

var backing = make([]int, 15) // 15 elements
var start int

func prepend(dest []int, value int) []int {
    if start == 0 {
        // No more room for new value, must allocate bigger backing array:
        newbacking := make([]int, len(backing)+5)
        start = 5
        copy(newbacking[5:], backing)
        backing = newbacking
    }

    start--
    dest = backing[start : start+len(dest)+1]
    dest[0] = value
    return dest
}

测试/使用它：

start = 5
s := backing[start:start] // empty slice, starting at idx=5
s = append(s, 1, 2, 3, 4)
fmt.Println(s)
s = prepend(s, 9)
fmt.Println(s)
s = prepend(s, 8)
fmt.Println(s)

// Prepend more to test reallocation:
for i := 10; i < 15; i++ {
    s = prepend(s, i)
}
fmt.Println(s)

输出（在 Go Playground 上尝试）：

[1 2 3 4]
[9 1 2 3 4]
[8 9 1 2 3 4]
[14 13 12 11 10 8 9 1 2 3 4]

分析：当 backing 切片中有空间来添加值时，此解决方案不进行任何分配和复制！ 所发生的只是创建一个新的从覆盖目标的 backing 切片中切片 +1 space 作为要添加的值，设置它和 returns 这个切片值。没有比这更好的了。

如果没有空间，则分配更大的backing片，复制旧的内容，然后"normal"前置。

使用棘手的切片

想法：假设你总是以倒序的方式将元素存储在一个切片中。

在切片中以倒序存储元素意味着 prepand 变为追加！

所以对于"prepand"一个元素，你可以简单地使用append(s, value)。仅此而已。

是的，这有其有限的用途（例如，附加到以相反顺序存储的切片与 "normal" 切片和前置操作具有相同的问题和复杂性），并且您失去了许多便利（能够列出使用 for range 的元素仅举一个例子），但在性能方面，没有什么比使用 append().

预填充值更好的了

注意：遍历倒序存储元素的元素必须使用向下循环，例如：

for i := len(s) - 1; i >= 0; i-- {
    // do something with s[i]
}

最后说明：所有这些解决方案都可以很容易地扩展到前置一个切片而不仅仅是一个值。通常，当重新切片时附加的 space 不是 +1 而是 +len(values)，并且不是简单地设置 dst[0] = value 而是调用 copy(dst, values).

Go中使用append前置的机制是什么？

What is the mechanism of using append to prepend in Go?

memory-management

append

go

slice

prepend

重新切片和复制

有链表

手动管理更大的后备阵列

使用棘手的切片