在golang追加的大O [英] Big O of append in golang

问题描述

什么是旅途中的内置的复杂性追加功能？有关使用字符串连接什么 + ？

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 说，如果目标有足够的能力，那么这片是 resliced​​ 。我希望reslicing是一个常数时间的操作。我也希望同样适用于字符串连接使用 + 。

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 +.

推荐答案

这一切都取决于所使用的实际执行情况，但我这个基础上的标准去以及gccgo。

This all depends on the actual implementation used, but I'm basing this on the standard Go as well as gccgo.

片

Reslicing指在一个结构变化的一个整数（片是三个域的结构：长度，容量和指针支持内存）

Reslicing means changing an integer in a struct (a slice is a struct with three fields: length, capacity and pointer to backing memory).

如果切片不具有足够的容量，追加将需要分配新的内存和复制旧以上。对于片＆LT; 1024个元素，这将增加一倍的容量，对于> 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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！