英文:
Big O of append in Golang
问题
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 中提到，如果目标切片有足够的容量，那么该切片将被“重新切片”。我希望“重新切片”是一个常数时间操作。我也希望对使用+进行字符串连接的情况也是如此。
英文:
What is the complexity of Go's builtin append function? What about string concatenation using +?
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 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 +.
答案1
得分: 26
这完全取决于实际使用的实现方式，但我基于标准的Go和gccgo进行了基础。
切片
重新切片意味着改变结构体中的一个整数（切片是一个具有三个字段的结构体：长度、容量和指向支持内存的指针）。
如果切片的容量不足，追加操作将需要分配新的内存并将旧内存复制过去。对于长度小于1024的切片，容量将加倍，对于长度大于1024的切片，容量将增加1.25倍。
字符串
由于字符串是不可变的，每次使用+进行字符串连接都会创建一个新的字符串，这意味着复制旧字符串。因此，如果在循环中执行N次连接操作，将会分配N个字符串并复制内存N次。
英文:
This all depends on the actual implementation used, but I'm basing this on the standard Go as well as gccgo.
Slices
Reslicing means changing an integer in a struct (a slice is a struct with three fields: length, capacity and pointer to backing memory).
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.
Strings
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论