Was ist die zeitliche Komplexität von „append' in Go?

Komplexität in Go anhängen

Problem:

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

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

Führt die Anhängeoperation in linearer Zeit oder in amortisierter Konstante durch Zeit?

Antwort:

Die Go-Programmiersprachenspezifikation besagt, dass append bei Bedarf eine Neuzuweisung durchführt:

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.

Der spezifische Algorithmus ist jedoch zu Das Erweitern des Ziel-Slices bei Bedarf hängt von der Implementierung ab. Für den aktuellen GC-Compiler ist der Algorithmus eine amortisierte konstante Zeit.

Amortisierte konstante Zeit Erklärung:

Die Slice-Kapazität wird auf gierige Weise erhöht:

• Wenn die alte Kapazität mehr als das Doppelte der alten Kapazität beträgt, wird die neue Kapazität auf die alte gesetzt Kapazität.
• Andernfalls, wenn die alte Länge kleiner als 1024 ist, wird die neue Kapazität auf das Doppelte der alten Kapazität eingestellt.
• Andernfalls wird die neue Kapazität um ein Viertel erhöht, bis sie erreicht ist Mindestens die Größe der alten Kapazität.

Dieser Ansatz stellt sicher, dass die gesamte für die Neuzuweisung aufgewendete Zeit auf O(n) amortisiert wird, wobei n die Länge ist des resultierenden Slice.

Überlegungen zur Implementierung:

Die Go-Sprachspezifikation ermöglicht verschiedene Implementierungen von append. Beispielsweise kann die Umsetzung großzügig (Zuweisung von mehr als dem erforderlichen Mindestbetrag) oder sparsam (Zuweisung des erforderlichen Mindestbetrags) sein. Der Go-GC-Compiler verwendet einen großzügigen dynamischen Array-amortisierten Konstantzeitalgorithmus.

Zusammenfassung:

Die Komplexität des Anhängens in Go hängt von der Implementierung ab. Allerdings verwenden gängige Implementierungen wie der Go gc-Compiler und gccgo amortisierte Algorithmen mit konstanter Zeit.

Das obige ist der detaillierte Inhalt vonWas ist die zeitliche Komplexität von „append' in Go?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!