Big O di append in golang

Question

Qual è la complessità della funzione integrata di go append? Che dire della concatenazione di stringhe usando +?

Vorrei rimuovere un elemento da una sezione aggiungendo due fette escludendo quell'elemento, es. 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 dice che se la destinazione ha una capacità sufficiente, allora quella fetta è resliced. Spero che "reslicing" sia un'operazione a tempo costante. Spero anche che lo stesso valga per la concatenazione di stringhe usando +.

Answer 1

Questo dipende dall'attuale implementazione utilizzata, ma lo sto basando sullo standard Go e su gccgo.

Fette

Reslicing significa cambiare un numero intero in una struttura (una fetta è una struttura con tre campi: lunghezza, capacità e puntatore al backup memoria).

Se la sezione non ha una capacità sufficiente, append dovrà allocare nuova memoria e copiare quella precedente. Per le sezioni con elementi < 1024, raddoppierà la capacità, per le sezioni con> 1024 elementi lo aumenterà del fattore 1,25.

Strings

Poiché le stringhe sono immutabili, ogni concatenazione di stringhe con + creerà una nuova stringa, il che significa che la copia di quello vecchio. Quindi, se lo fai N volte in un ciclo, dovrai allocare N stringhe e copiare la memoria circa N volte.