Golang中追加的大O [英] Big O of append in Golang

问题描述

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 个元素的切片，它将使容量翻倍，对于具有 >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屋！