追加复杂性 [英] `append` complexity
问题描述
var a [] int
在Go编程语言中，这个循环的计算复杂度是多少？对于i：= 0;我< n; i ++ {
a = append（a，i）
}
<$> c $ c> append 在线性时间内操作（重新分配内存并复制每个append中的所有内容），或者在分期固定的时间内（像实现许多语言中的vector类一样）？ b $ b
Go Programming Language Specification 表示如果需要， append 内置函数会重新分配。
如果s的容量不足以适应附加值，
append将分配一个新的，足够大的分片，以适合
现有分片元素和附加值。因此，返回的
切片可能引用不同的基础数组。
生成目标切片的精确算法，必要的，对于追加是依赖于实现的。对于当前的 gc 编译器算法，请参阅Go runtime 中的 growslice 函数c $ c> package slice.go 源文件。这是分期不变的时间。
部分地，数量增长切片计算结果如下：
newcap：= old.cap
doublecap：= newcap + newcap
if cap> doublecap {
newcap = cap
} else {
if old.len< 1024 {
newcap = doublecap
} else {
for newcap< {
newcap + = newcap / 4
}
}
}
ADDENDUM
Go Programming Language规范允许该语言的实现者以多种方式实现 append 内置函数。
<例如，新的分配只需要足够大。分配的金额可能是parsimonius，分配最低必要金额或慷慨，分配超过最低必要金额以最小化多次调整大小的成本。 Go
gc 编译器使用一个慷慨的动态数组分段常量时间算法。下面的代码演示了两个合法的实现： 追加内置函数。慷慨的常量函数实现与Go gc 编译器相同的分摊常量时间算法。一旦初始分配被填充，parsimonius变量函数每次都重新分配和复制所有内容。 Go append 函数和Go gccgo 编译器用作控件。 package main
导入fmt
//大量重新分配
func常量（s []） int，x ... int）[] int {
if len（s）+ len（x）> cap（s）{
newcap：= len（s）+ len（x）
m：= cap（s）
如果m + m < newcap {
m = newcap
} else {
for {
if len（s）< 1024 {
m + = m
} else {
m + = m / 4
}
if！（m
$ b tmp：= make（[] int，len（s），m）
copy（tmp，s）
s = tmp
}
如果len（s）+ len（x）>上限（
panic（unreachable）
}
返回追加（s，x ...）
}
// Parsimonious重新分配
func变量（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
}
如果len（s）+ len（x）>上限（
panic（unreachable）
}
返回追加（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;我< 4096; i ++ {
a = append（a，x ...）
c =常数（c，x ...）
v =变量（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））
}
$ b $输出：$ g $：
$ b $
data 3 3 [0 1 2] 2 2 [3 4]
追加8195 9152 2
常数8195 9152 2
变量8195 8195 2
gccgo：
数据3 3 [0 1 2] 2 2 [3 4]
追加8195 9152 2
常数8195 9152 2
变量8195 8195 2
总而言之，根据实施情况，一旦初始容量被填充，内置追加>函数可能会或可能不会在每次调用时重新分配。
参考文献：
如果s的容量不足以容纳附加值，则
append分配一个新的足够大的切片，它适合
现有切片元素和附加值。因此，返回的
切片可能引用不同的基础数组。
规范（在tip和1.0.3 ）状态：
如果s的容量不足以适应额外的
值，那么append分配一个新的，足够大的切片，该切片适合
既有切片元素和附加值。因此，
返回的切片可能引用不同的基础数组。
这应该是如果且仅当？例如，如果我知道我的slice的
容量足够长，我确信我会
不更改底层数组吗？
是的，你很放心。
运行时 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屋！
