Big O von append in golang

Question

Was ist die Komplexität von go eingebaut append Funktion? Was ist mit String-Verkettung mit +?

Ich möchte ein Element aus einem Slice entfernen, indem Sie zwei Segmente mit Ausnahme dieses Elements anfügen, z. http://play.golang.org/p/RIR5fXq-Sf

nums := []int{0, 1, 2, 3, 4, 5, 6, 7} 
fmt.Println(append(nums[:4], nums[5:]...)) 

=> [0 1 2 3 5 6 7] 

http://golang.org/pkg/builtin/#append sagt, dass, wenn das Ziel eine ausreichende Kapazität hat, dann wird diese Scheibe resliced ist. Ich hoffe, dass "Reslicing" eine konstante Zeitoperation ist. Ich hoffe auch das gleiche gilt für String-Verkettung mit +.

Answer 1

Dies hängt alles von der tatsächlichen Implementierung verwendet, aber ich basiere dies auf dem Standard Go sowie GCCGO.

Scheiben

Reslicing bedeutet eine ganze Zahl in einem struct ändert (eine Scheibe eine Struktur mit drei Feldern: Länge, Kapazität und Zeigerspeicher zu sichern).

Wenn der Slice nicht über ausreichende Kapazität verfügt, muss append neuen Speicher zuweisen und den alten kopieren. Für Slices mit < 1024 Elementen wird die Kapazität verdoppelt, für Slices mit> 1024 Elementen wird sie um den Faktor 1,25 erhöht.

Strings

Da Strings unveränderlich ist, jede String-Verkettung mit + wird eine neue Zeichenfolge erstellen, die die alten Kopiermittel. Also, wenn Sie es N-mal in einer Schleife tun, werden Sie N Strings zuweisen und Speicher um N mal kopieren.