`złożoność złożoności

Question

Jaka jest złożoność obliczeniowa tej pętli w języku programowania Go?

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

Czy append działać w czasie liniowym (realokacji pamięci i kopiując wszystko na każdym dołącz) lub w skorygowanej stałym czasie (jak drogi klasy vector w wielu językach są implemnted)?

Answer 1

The Go Programming Language Specification mówi, że wbudowana funkcja append ponownie przydziela, jeśli to konieczne.

Appending to and copying slices

Jeśli pojemność s nie jest na tyle duża, aby zmieścić dodatkowe wartości, Dołącz przydziela nowy, wystarczająco duży kawałek, który pasuje zarówno istniejących elementów pokroić i dodatkowe wartości. Zatem zwrócony plaster może odnosić się do innej macierzy bazowej.

Precyzyjny algorytm do powiększania fragmentu docelowego, gdy jest to konieczne, w celu dołączenia jest zależny od implementacji. W przypadku bieżącego algorytmu kompilatora gc, zobacz funkcję growslice w pliku źródłowym Go runtime pakietu slice.go. Jest to amortyzowany stały czas.

W części, obliczanie kromka kwota w uprawie brzmi:

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

DODATEK

Go Programming Language Specification pozwala implementacji języka wdrożyć wbudowaną funkcję append na wiele sposobów.

Na przykład nowe alokacje muszą być "wystarczająco duże". Przydzielona kwota może być parsimonius, alokować minimalną niezbędną kwotę lub hojny, alokując więcej niż minimalną konieczną kwotę, aby zminimalizować wielokrotnie koszty zmiany rozmiaru. Kompilator Go gc używa hojnego dynamicznego algorytmu amortyzowanego w czasie stałym. Poniższy kod ilustruje dwie implementacje prawne wbudowanej funkcji append. Hojna funkcja stała implementuje ten sam zamortyzowany algorytm czasu stałego, co kompilator Go gc. Funkcja zmiennej parsimonius, gdy początkowa alokacja jest wypełniona, ponownie przydziela i kopiuje wszystko za każdym razem. Funkcja Go append i kompilator Go gccgo są używane jako elementy sterujące.

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

wyjściowa:

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 

Podsumowując, w zależności od implementacji, gdy początkowa pojemność jest napełnieniu append wbudowana w funkcji może, ale nie musi, zmieniać przydział dla każdego połączenia.

Odniesienia:

Dynamic array

Amortized analysis

Appending to and copying slices

Jeżeli pojemność s nie jest wystarczająco duża, aby dodatkowe wartości append przydziela nowy wystarczająco duża wycinek pasujący do istniejącego sl. elementy lodu i dodatkowe wartości. Zatem zwrócony plaster może odnosić się do innej macierzy bazowej.

Append to a slice specification discussion

Spec (w końcówce i 1.0.3) stwierdza:

„Jeśli pojemność s nie jest na tyle duża, aby zmieścić dodatkowe wartości , append przydziela nowy, wystarczająco duży kawałek która pasuje zarówno do istniejących elementów plasterka, jak i do dodatkowych wartości, zatem zwracany segment może odnosić się do innej podstawowej tablicy. "

Czy powinno to być "Jeśli i tylko jeśli"? Na przykład, jeśli wiem, że pojemność mojego plasterka jest wystarczająca, czy mogę zagwarantować, że nie zmieni podstawowej tablicy?

Rob Pike

Tak masz więc zapewnione.

Runtime slice.go plik źródłowy

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

Answer 2

Nie realokacji na każdy dołączania i to całkiem wyraźnie stwierdzono w docs:

Jeśli pojemność s nie jest na tyle duża, aby zmieścić dodatkowe wartości, dołącz przydziela nowy, wystarczająco duża plaster pasujący zarówno do istniejących elementów plasterka, jak i do dodatkowych wartości. Zatem zwracany segment może odwoływać się do innej podstawowej tablicy.

Amortyzowany stały czas jest zatem złożonością, o którą pytano.