Golang中append的时间复杂度（Big O）

Question

13

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 的说明是，如果目标切片有足够的容量，则会对该切片进行 重新切片。我希望 "重新切片" 是一个常数时间操作。我也希望对于使用 + 进行字符串连接的情况，情况与此相同。

- Kaleidoscope

一些关于行为的参考：http://criticalindirection.com/2016/02/17/slice-with-a-pinch-of-salt/ - user31986

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dominik Honnef · Accepted Answer

所有这些都取决于实际的实现方式，但我基于标准的Go和gccgo进行解释。

切片

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

如果切片没有足够的容量，追加操作将需要分配新的内存并复制旧的内存。对于元素数小于1024的切片，它将使其容量翻倍；对于元素数大于1024的切片，它将增加1.25倍。

字符串

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