问题描述
Go 内置的 append 函数的复杂度是多少?使用 + 进行字符串连接怎么样?
What is the complexity of Go's builtin append function? What about string concatenation using +?
我想通过添加不包括该元素的两个切片来从切片中删除一个元素，例如.http://play.golang.org/p/RIR5fXq-Sf
I'd like to remove an element from a slice by appending two slices excluding that element, ex. 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 说如果目的地有足够的容量，则该切片被重新切片.我希望重新切片"是一个恒定的时间操作.我也希望同样适用于使用 + 的字符串连接.
http://golang.org/pkg/builtin/#append says that if the destination has sufficient capacity, then that slice is resliced. I'm hoping that "reslicing" is a constant time operation. I'm also hoping the same applies to string concatenation using +.
推荐答案
这完全取决于所使用的实际实现，但我是基于标准的 Go 和 gccgo.
This all depends on the actual implementation used, but I'm basing this on the standard Go as well as gccgo.
切片
重新切片意味着更改结构体中的整数(切片是具有三个字段的结构体:长度、容量和指向后备内存的指针).
Reslicing means changing an integer in a struct (a slice is a struct with three fields: length, capacity and pointer to backing memory).
如果slice没有足够的容量，append需要分配新的内存，把旧的拷贝过来.对于 1024 个元素的切片，它将增加 1.25 倍.
If the slice does not have sufficient capacity, append will need to allocate new memory and copy the old one over. For slices with <1024 elements, it will double the capacity, for slices with >1024 elements it will increase it by factor 1.25.
字符串
由于字符串是不可变的，每个字符串与 + 的连接都会创建一个新字符串，这意味着复制旧字符串.因此，如果您在循环中执行 N 次，您将分配 N 个字符串并复制大约 N 次内存.
Since strings are immutable, each string concatenation with + will create a new string, which means copying the old one. So if you're doing it N times in a loop, you will allocate N strings and copy memory around N times.
这篇关于Golang中追加的大O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！