Go编程语言中此循环的计算复杂度是多少?
var a []int for i := 0 ; i < n ; i++ { a = append(a, i) }
并append以线性时间(重新分配内存和每个追加拷贝的一切),或在固定的时间里操作(比如在许多语言方式矢量类是implemnted)?
append
Go编程语言规范说,append如果需要,内置函数会重新分配。
附加并复制切片 如果s的容量不足以容纳附加值,则append分配一个新的,足够大的切片,使其既适合现有slice元素又适合附加值。因此,返回的切片可以引用不同的基础数组。
附加并复制切片
如果s的容量不足以容纳附加值,则append分配一个新的,足够大的切片,使其既适合现有slice元素又适合附加值。因此,返回的切片可以引用不同的基础数组。
必要时,增加目标切片的精确算法取决于实现。有关当前的gc编译器算法,请参见growsliceGo runtime包slice.go源文件中的函数。固定时间摊销。
gc
growslice
runtime
slice.go
增长量切片计算部分读取:
newcap := old.cap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { if old.len < 1024 { newcap = doublecap } else { for newcap < cap { newcap += newcap / 4 } } }
附录
在围棋编程语言规范允许语言的实现者来实现append的内置功能在许多方面。
例如,新的分配仅必须“足够大”。分配的数量可以是parsimonius(分配最小的必要数量),或者是慷慨的,分配的数量大于最小必需的数量,以使多次调整大小的成本最小化。Go gc编译器使用大量的动态数组摊销恒定时间算法。
以下代码说明了append内置函数的两种合法实现。慷慨的常量函数实现了与Go gc编译器相同的摊销常量时间算法。一旦完成了初始分配,parsimonius变量函数便会重新分配并复制所有内容。Go append函数和Go gccgo编译器用作控件。
gccgo
package main import "fmt" // Generous reallocation func constant(s []int, x ...int) []int { if len(s)+len(x) > cap(s) { newcap := len(s) + len(x) m := cap(s) if m+m < newcap { m = newcap } else { for { if len(s) < 1024 { m += m } else { m += m / 4 } if !(m < newcap) { break } } } tmp := make([]int, len(s), m) copy(tmp, s) s = tmp } if len(s)+len(x) > cap(s) { panic("unreachable") } return append(s, x...) } // Parsimonious reallocation func variable(s []int, x ...int) []int { if len(s)+len(x) > cap(s) { tmp := make([]int, len(s), len(s)+len(x)) copy(tmp, s) s = tmp } if len(s)+len(x) > cap(s) { panic("unreachable") } return append(s, x...) } func main() { s := []int{0, 1, 2} x := []int{3, 4} fmt.Println("data ", len(s), cap(s), s, len(x), cap(x), x) a, c, v := s, s, s for i := 0; i < 4096; i++ { a = append(a, x...) c = constant(c, x...) v = variable(v, x...) } fmt.Println("append ", len(a), cap(a), len(x)) fmt.Println("constant", len(c), cap(c), len(x)) fmt.Println("variable", len(v), cap(v), len(x)) }
输出:
GC:
data 3 3 [0 1 2] 2 2 [3 4] append 8195 9152 2 constant 8195 9152 2 variable 8195 8195 2
gccgo:
总而言之,取决于实现方式,一旦初始容量已满,append内置函数可能会或可能不会在每次调用时重新分配。
参考文献:
动态数组
摊销分析
附加并复制切片 如果s的容量不足以适合附加值,请 append分配一个新的足够大的切片,使其既适合现有slice元素又适合附加值。因此,返回的切片可以引用不同的基础数组。 附加到切片规范讨论 规范(技巧和1.0.3)指出: “如果s的容量不足以容纳其他值,则append分配一个新的,足够大的切片,使其既适合现有slice元素又适合附加值。因此,返回的切片可能引用了另一个基础数组。” 这应该是“如果且仅当”吗?例如,如果我知道切片的容量足够长,是否可以确定不会更改基础数组? 罗伯·派克 是的,你很放心。
如果s的容量不足以适合附加值,请 append分配一个新的足够大的切片,使其既适合现有slice元素又适合附加值。因此,返回的切片可以引用不同的基础数组。
附加到切片规范讨论
规范(技巧和1.0.3)指出:
“如果s的容量不足以容纳其他值,则append分配一个新的,足够大的切片,使其既适合现有slice元素又适合附加值。因此,返回的切片可能引用了另一个基础数组。”
这应该是“如果且仅当”吗?例如,如果我知道切片的容量足够长,是否可以确定不会更改基础数组?
罗伯·派克
是的,你很放心。
运行时slice.go源文件
数组,切片(和字符串):“追加”的机制