为了账号安全,请及时绑定邮箱和手机立即绑定

在 Go 中重构切片是一个恒定时间操作吗?

在 Go 中重构切片是一个恒定时间操作吗?

Go
有只小跳蛙 2022-06-21 10:41:24
[x, y]我在 Go中有一个坐标对 ( ) 的 FIFO 队列:type Copair [2]inttype Queue []Copairvar 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:]我正在重新构建切片,理论上它应该只需要在内存中更改一个地址,因此是一个恒定时间的操作。现在,我们正在逐渐丢失堆上的字节(或者谁知道,Go 的逃逸分析可能足够聪明,可以将它放在堆栈上),我希望垃圾收集器可以回收这些字节以避免内存泄漏,最终我们将到达堆边界,运行时将不得不将整个队列复制到其他地方,这肯定是线性时间操作。但...切片重构是通过q = q[1:]恒定时间操作执行的,还是与队列大小成线性关系?如果(我怀疑)答案是 oh-so-very-Go “它取决于”,它依赖的条件是什么,是否有任何简单的经验法则可以解决这个问题?
查看完整描述

2 回答

?
杨__羊羊

TA贡献1943条经验 获得超7个赞

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



查看完整回答
反对 回复 2022-06-21
?
慕标5832272

TA贡献1966条经验 获得超4个赞

q[1:]是一个切片表达式,它“无非”只是创建一个新的切片头,即reflect.SliceHeader. 它只是 3 个整数值。

当然会检查索引范围,例如,如果q切片为空,则会导致运行时恐慌。


查看完整回答
反对 回复 2022-06-21
  • 2 回答
  • 0 关注
  • 117 浏览
慕课专栏
更多

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信