`追加`复杂性 [英] `append` complexity
问题描述
这个循环在 Go 编程语言中的计算复杂度是多少?
var a []int对于 i := 0 ;我＜;我++ {a = 追加(a, i)}append 是在线性时间内操作(重新分配内存并复制每个 append 上的所有内容)，还是在分摊的常量时间内(如许多语言中的向量类的实现方式)?
Go 编程语言规范 说append 内置函数在必要时重新分配.
如果 s 的容量不够大，无法容纳附加值，append 分配一个新的、足够大的切片，既适合现有切片元素和附加值.因此，返回的slice 可能引用不同的底层数组.
必要时，用于扩展目标切片的精确算法取决于实现.当前gc编译器算法见Goruntime包中的growslice函数slice.go 源文件.它是摊销的常数时间.
部分地，切片增长量计算如下:
newcap := old.capdoublecap := newcap + newcap如果上限 >双盖{newcap = 上限} 别的 {如果 old.len <1024 {新帽 = 双帽} 别的 {对于 newcap <帽{新上限 += 新上限/4}}}附录
Go 编程语言规范 允许该语言的实现者实现 append 多种方式的内置函数.
例如，新的分配只需要足够大".分配的数量可能是简约的，分配最小的必要数量，或者慷慨的，分配超过最小必要的数量，以最小化多次调整大小的成本.Go gc 编译器使用了一个慷慨的动态数组分摊常量时间算法.
以下代码说明了 append 内置函数的两个合法实现.慷慨的常量函数实现了与 Go gc 编译器相同的分摊常量时间算法.parsimonius 变量函数，一旦初始分配被填满，每次都会重新分配和复制所有内容.Go append 函数和 Go gccgo 编译器用作控件.
包主导入fmt"//慷慨的重新分配func 常量(s []int, x ...int) []int {如果 len(s)+len(x) >上限{newcap := len(s) + len(x)m := 上限如果 m+m <新帽{m = 新盖帽} 别的 {为了 {如果 len(s) <1024 {米 += 米} 别的 {米 += 米/4}如果 !(m < newcap) {休息}}}tmp := make([]int, len(s), m)复制(tmp，s)s = tmp}如果 len(s)+len(x) >上限{恐慌(无法访问")}返回 append(s, x...)}//简约的重新分配func 变量(s []int, x ...int) []int {如果 len(s)+len(x) >上限{tmp := make([]int, len(s), len(s)+len(x))复制(tmp，s)s = tmp}如果 len(s)+len(x) >上限{恐慌(无法访问")}返回 append(s, x...)}功能主(){s := []int{0, 1, 2}x := []int{3, 4}fmt.Println("数据", len(s), cap(s), s, len(x), cap(x), x)a, c, v := s, s, s对于我:= 0;我＜4096;我++ {a = append(a, x...)c = 常数(c, x...)v = 变量(v, x...)}fmt.Println("追加", len(a), cap(a), len(x))fmt.Println("常量", len(c), cap(c), len(x))fmt.Println("变量", len(v), cap(v), len(x))}输出:
GC:
数据 3 3 [0 1 2] 2 2 [3 4]附加 8195 9152 2常数 8195 9152 2变量 8195 8195 2gccgo:
数据 3 3 [0 1 2] 2 2 [3 4]附加 8195 9152 2常数 8195 9152 2变量 8195 8195 2总而言之，根据实现，一旦初始容量被填满，append 内置函数可能会也可能不会在每次调用时重新分配.
参考文献:
<块引用>如果 s 的容量不够大，无法容纳附加值，append 分配一个新的、足够大的切片，既适合现有切片元素和附加值.因此，返回的slice 可能引用不同的底层数组.
规范(在提示和 1.0.3 中)指出:
"如果s的容量不足以容纳额外的值，append 分配一个新的、足够大的切片以适合现有切片元素和附加值.就这样返回的切片可能引用不同的底层数组."
这应该是当且仅当"吗?例如，如果我知道我切片的容量足够长，我敢保证我会不改变底层数组?
是的，你很放心.
运行时 slice.go 源文件>
What is the computational complexity of this loop in the Go programming language?
var a []int
for i := 0 ; i < n ; i++ {
a = append(a, i)
}
Does append operate in linear time (reallocating memory and copying everything on each append), or in amortized constant time (like the way vector classes in many languages are implemnted)?
The Go Programming Language Specification says that the append built-in function reallocates if necessary.
Appending to and copying slices
If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.
The precise algorithm to grow the target slice, when necessary, for an append is implementation dependent. For the current gc compiler algorithm, see the growslice function in the Go runtime package slice.go source file. It's amortized constant time.
In part, the amount-to-grow slice computation reads:
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
}
}
}
ADDENDUM
The Go Programming Language Specification allows implementors of the language to implement the append built-in function in a number of ways.
For example, new allocations only have to be "sufficiently large". The amount allocated may be parsimonius, allocating the minimum necessary amount, or generous, allocating more than the minimum necessary amount to minimize the cost of resizing many times. The Go gc compiler uses a generous dynamic array amortized constant time algorithm.
The following code illustrates two legal implementations of the append built-in function. The generous constant function implements the same amortized constant time algorithm as the Go gc compiler. The parsimonius variable function, once the initial allocation is filled, reallocates and copies everything every time. The Go append function and the Go gccgo compiler are used as controls.
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))
}
Output:
gc:
data 3 3 [0 1 2] 2 2 [3 4]
append 8195 9152 2
constant 8195 9152 2
variable 8195 8195 2
gccgo:
data 3 3 [0 1 2] 2 2 [3 4]
append 8195 9152 2
constant 8195 9152 2
variable 8195 8195 2
To summarize, depending on the implementation, once the initial capacity is filled, the append built-in function may or may not reallocate on every call.
References:
Appending to and copying slices
If the capacity of s is not large enough to fit the additional values,
appendallocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array.Append to a slice specification discussion
The spec (at tip and 1.0.3) states:
"If the capacity of s is not large enough to fit the additional values,
appendallocates a new, sufficiently large slice that fits both the existing slice elements and the additional values. Thus, the returned slice may refer to a different underlying array."Should this be an "If and only if"? For example, if I know the capacity of my slice is sufficiently long, am I assured that I will not change the underlying array?
Yes you are so assured.
runtime slice.go source file
Arrays, slices (and strings): The mechanics of 'append'
这篇关于`追加`复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
