go - Golang中追加的大O

Question

Go 的内置append函数的复杂度是多少？使用 字符串连接怎么样+？

我想通过附加两个不包括该元素的切片来从切片中删除一个元素，例如。http://play.golang.org/p/RIR5fXq-Sf

nums := []int{0, 1, 2, 3, 4, 5, 6, 7}
fmt.Println(append(nums[:4], nums[5:]...))

=> [0 1 2 3 5 6 7]

http://golang.org/pkg/builtin/#append说如果目的地有足够的容量，那么那个切片就是resliced. 我希望“重新切片”是一个恒定的时间操作。我也希望这同样适用于使用+.

Answer 1

这一切都取决于使用的实际实现，但我基于标准 Go 以及 gccgo。

切片

重新切片意味着更改结构中的整数（切片是具有三个字段的结构：长度、容量和指向后备内存的指针）。

如果 slice 没有足够的容量，append 将需要分配新的内存并将旧的复制过来。对于具有 <1024 个元素的切片，它将增加一倍容量，对于具有 >1024 个元素的切片，它将增加 1.25 倍。

字符串

由于字符串是不可变的，每个字符串连接+都会创建一个新字符串，这意味着复制旧字符串。因此，如果您在循环中执行 N 次，您将分配 N 个字符串并复制大约 N 次内存。