`append`複雜度

Question

Go編程語言中該循環的計算複雜度是多少？

var a []int 
for i := 0 ; i < n ; i++ { 
    a = append(a, i) 
} 

是否append線性時間操作（重新分配內存和複製在每個附加的所有內容），或在分期常量時間（喜歡的方式在許多語言矢量類implemnted）？

Answer 1

The Go Programming Language Specification說，append內置函數，如果有必要重新分配。

Appending to and copying slices

如果s的容量不夠大，以適應更多的價值， 追加分配一個新的，足夠大的切片適合兩個 現有切片元素和附加價值。因此，返回的 切片可能指代不同的基礎陣列。

在必要時增加目標切片的精確算法對於追加是依賴於實現的。有關當前的gc編譯器算法，請參閱Go runtime包slice.go源文件中的growslice函數。這是攤銷不變的時間。

在某種程度上，量到成長切片計算如下：

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 
      } 
     } 
} 

附錄

的Go Programming Language Specification允許語言的實現者實現多種方式的append內置功能。

例如，新的分配只需要「足夠大」。分配的金額可能是parsimonius，分配最低必要金額或慷慨，分配超過最低必要金額以最小化多次調整大小的成本。 Go gc編譯器使用慷慨的動態數組分攤恆定時間算法。

以下代碼說明了append內置函數的兩個合法實現。慷慨的常量函數實現與編譯器相同的分攤恆定時間算法。一旦初始分配被填充，parsimonius變量函數每次都重新分配和複製所有內容。 Go append函數和Go 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：

data  3 3 [0 1 2] 2 2 [3 4] 
append 8195 9152 2 
constant 8195 9152 2 
variable 8195 8195 2 

總之，這取決於實施方式，一旦初始容量被填滿時，append內置in函數可能會或可能不會在每次調用時重新分配。

參考文獻：

Dynamic array

Amortized analysis

Appending to and copying slices

如果s的容量不夠大，以適應更多的價值， append分配一個新的，足夠大的切片適合現有sl的 冰元素和附加值。因此，返回的 切片可能指代不同的基礎陣列。

Append to a slice specification discussion

該規範（在塞尖和1.0.3）規定：

「如果s的容量不夠大，以適應附加的 值，append分配一個新的，足夠大的片這適合 現有切片元素和附加值。因此， 返回的切片可能引用不同的基礎數組。

這應該是「如果且僅當」？例如，如果我知道我的片的容量足夠長，我確信我會 不更改底層數組？

Rob Pike

是的，你是如此放心。

運行slice.go源文件

Arrays, slices (and strings): The mechanics of 'append'

Answer 2

它不重新分配在每個追加，它是相當明確的docs說：

如果s的容量不夠大，以適應更多的價值，追加分配一個新的，足夠大的切片適合現有切片元素和附加值。因此，返回的片可能會引用不同的底層數組。

分期常量時間，因此是問的複雜性。