`append` complex

Question

Qual è la complessità computazionale di questo ciclo nel linguaggio di programmazione Go?

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

Does append operare in tempo lineare (riallocando la memoria e la copia di tutto ciò che su ogni append), o in ammortizzato costante di tempo (come il modo in cui le classi vettoriali in molte lingue sono implemnted)?

Answer 1

The Go Programming Language Specification dice che la funzione incorporata append si rialloca se necessario.

Appending to and copying slices

Se la capacità di s non è abbastanza grande da contenere i valori aggiuntivi, accodamento assegna una nuova sufficientemente grande fetta, che si adatta sia gli elementi fetta esistenti ei valori aggiuntivi. Pertanto, la porzione restituita può fare riferimento a un diverso array sottostante.

L'algoritmo preciso per aumentare la porzione di destinazione, quando necessario, per un'appendice dipende dall'implementazione. Per l'algoritmo del compilatore gc corrente, vedere la funzione growslice nel file di origine del pacchetto slice.go. È ammortizzato tempo costante.

In parte, la fetta di calcolo dell'importo da coltivare legge:

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

ADDENDUM

Il Go Programming Language Specification permette implementatori del linguaggio per implementare la funzione built-in append in un certo numero di modi.

Ad esempio, le nuove allocazioni devono essere "sufficientemente grandi". L'importo assegnato può essere parsimonioso, assegnando l'importo minimo necessario o generoso, assegnando più dell'importo minimo necessario per ridurre al minimo il costo del ridimensionamento più volte. Il compilatore Go gc utilizza un algoritmo a tempo costante ammortizzato con un array dinamico generoso.

Il seguente codice illustra due implementazioni legali della funzione integrata append. La generosa funzione costante implementa lo stesso algoritmo a tempo costante ammortizzato del compilatore Go gc. La funzione variabile parsimonius, una volta riempita l'allocazione iniziale, rialloca e copia tutto ogni volta. La funzione Go append e il compilatore Go gccgo vengono utilizzati come controlli.

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

uscita:

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 

In sintesi, a seconda dell'implementazione, una volta che la capacità iniziale viene riempito, il append incorporato in funzione può o non può riallocare su ogni chiamata.

Riferimenti:

Dynamic array

Amortized analysis

Appending to and copying slices

Se la capacità di s non è abbastanza grande da contenere i valori aggiuntivi, append alloca un nuovo, sufficientemente grande fetta che si adatta sia alla sl esistente elementi di ghiaccio e i valori aggiuntivi. Pertanto, la porzione restituita può fare riferimento a un diverso array sottostante.

Append to a slice specification discussion

Le specifiche (a punta e 1.0.3) dichiara:

"Se la capacità di s non è grande abbastanza da contenere i supplementari valori, append assegna un nuovo, sufficientemente grande fetta che si adatta a sia gli elementi di sezione esistenti che i valori aggiuntivi, pertanto la porzione restituita di potrebbe fare riferimento a un diverso array sottostante. "

Questo dovrebbe essere "Se e solo se"? Ad esempio, se so che la capacità della mia slice di è sufficientemente lunga, sono certo che non modificherò la matrice sottostante? ?

Rob Pike

Sì siete così certi.

runtime slice.go file sorgente

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

Answer 2

Non ridistribuire su ogni aggiungere e è abbastanza esplicitamente indicato nella docs:

Se la capacità di s non è grande abbastanza da contenere i valori aggiuntivi, aggiungere assegna un nuovo, sufficientemente grande slice che si adatta sia agli elementi slice esistenti che ai valori aggiuntivi. Pertanto, la slice restituita può fare riferimento a un array sottostante diverso.

Il tempo costante ammortizzato è quindi la complessità richiesta.