`append` Komplexität

Question

Wie hoch ist die Rechenkomplexität dieser Schleife in der Programmiersprache Go?

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

Does append in linearer Zeit arbeiten (Speicher Neuzuweisung und auf jedem append alles Kopieren) oder in den fortgeführten Anschaffungs konstante Zeit (wie die Art und Weise Vektor-Klassen in vielen Sprachen implemnted sind)?

Answer 1

The Go Programming Language Specification besagt, dass die eingebaute Funktion append bei Bedarf neu zugewiesen wird.

Appending to and copying slices

Wenn die Kapazität der s nicht groß genug ist, um die zusätzlichen Werte passen, weist Anfügen eine neue, ausreichend große Scheibe, die sowohl die bestehenden Slice-Elemente und die zusätzlichen Werte paßt. Daher kann sich der zurückgegebene Slice auf ein anderes zugrunde liegendes Array beziehen.

Der genaue Algorithmus zum Erweitern des Zielschnitts, falls erforderlich, für einen Anhang ist implementierungsabhängig. Informationen zum aktuellen gc Compiler-Algorithmus finden Sie unter der growslice-Funktion in der Go runtime-Paket slice.go Quelldatei. Es ist amortisierte konstante Zeit.

zum Teil der Menge züchtende slice Berechnung lautet:

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

NACHTRAG

Die Go Programming Language Specification Implementierer der Sprache ermöglicht die append integrierte Funktion in einer Reihe von Möglichkeiten zu implementieren.

Zum Beispiel müssen neue Zuordnungen nur "ausreichend groß" sein. Der zugeteilte Betrag kann parsimonius sein, wobei der minimal notwendige Betrag zugewiesen wird, oder großzügig, wobei mehr als der minimal notwendige Betrag zugewiesen wird, um die Kosten der Größenveränderung viele Male zu minimieren. Der Go gc Compiler verwendet einen großzügigen dynamischen amortisierten konstanten Zeitalgorithmus.

Der folgende Code veranschaulicht zwei legale Implementierungen der integrierten Funktion append. Die großzügige konstante Funktion implementiert den gleichen amortisierten konstanten Zeitalgorithmus wie der Go gc Compiler. Die Parsimonius-Variablenfunktion, sobald die anfängliche Zuweisung gefüllt ist, weist jedes Mal neu zu und kopiert alles. Die Go append-Funktion und der Go gccgo-Compiler werden als Steuerelemente verwendet.

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 

Um zusammenzufassen, je nach Implementierung, einmal die Anfangskapazität gefüllt ist, die append eingebauten in Funktion kann oder kann nicht bei jedem Anruf neu zuweisen.

Referenzen:

Dynamic array

Amortized analysis

Appending to and copying slices

Wenn die Kapazität ist nicht groß genug ist, um die zusätzlichen Werte passen, weist append eine neue, ausreichend groß Scheibe, die sowohl die vorhandenen sl passt Eiselemente und die zusätzlichen Werte. Daher kann sich der zurückgegebene Slice auf ein anderes zugrunde liegendes Array beziehen.

Append to a slice specification discussion

Die spec (an der Spitze und 1.0.3) heißt es:

„Wenn die Kapazität von s nicht groß genug ist, um die zusätzlichen Werte zu passen, weist append einen neuen, ausreichend große slice das passt sowohl die vorhandenen Schichtelemente und die zusätzlichen Werte. So kann sich die zurückgegebene Schicht auf ein anderes zugrunde liegendes Array beziehen. "

Sollte dies ein "Wenn und nur wenn" sein? Zum Beispiel, wenn ich weiß, dass die Kapazität meiner Scheibe ausreichend lang ist, bin ich versichert, dass ich das zugrunde liegende Array nicht ändern werde?

Rob Pike

Ja, Sie sind so gewährleistet.

Laufzeit slice.go Quelldatei

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

Answer 2

Es umverteilen nicht auf jeder anhängen, und es ist ganz explizit in der docs erklärte:

Wenn die Kapazität ist nicht groß genug ist, um die zusätzlichen Werte zu passen, fügen Sie weist eine neue, ausreichend groß Scheibe, die sowohl zu den vorhandenen Scheibenelementen als auch zu den zusätzlichen Werten passt. Daher kann sich das zurückgegebene Slice auf ein anderes zugrunde liegendes Array beziehen.

Amortisierte konstante Zeit ist somit die Komplexität gefragt.