go - 在 Go 中重构 slice 是一个恒定时间操作吗？

Question

我在 Go 中有一个坐标对 ([x, y]) 的 FIFO 队列:

type Copair [2]int
type Queue []Copair
var q = Queue{ ... preloaded values ... }

API 定义如下，其中重要的部分是 pop()功能:

func (q Queue) push(p Copair) {
    q = append(q, p)
}

func (q Queue) pop() (error, Copair) {
    if q != nil && len(q) >= 1 {
        q = q[1:]
        return nil, q[0]
    } else {
        return errors.New("index out of range [0]"), nil
    }
}

在那 q = q[1:]我正在重新构建 slice ，理论上它应该只需要在内存中更改一个地址，因此是一个恒定时间操作。现在，我们正在逐渐丢失堆上的字节(或者谁知道，Go 的逃逸分析可能足够聪明，可以将它放在堆栈上)，我希望垃圾收集器可以回收这些字节以避免内存泄漏，最终我们将到达堆边界，运行时将不得不将整个队列复制到其他地方，这肯定是线性时间操作。但... q = q[1:] 是否进行了 slice 重构一个恒定时间的操作，还是与队列的大小成线性关系？如果(我怀疑)答案是“它取决于”，那么它取决于什么条件，是否有任何简单的经验法则可以解决这个问题？

Answer 1

slice 是一个恒定时间的操作。 slice 头包含指向底层数组、大小和容量的指针。操作q:=q[1:]只需使用调整后的数组指针、大小和容量创建一个新 header 。