Big O z dołączenia do golang

Question

Jaka jest złożoność funkcji wbudowanej go w wersji append? A co z konkatenacją ciągów przy użyciu +?

Chciałbym usunąć element z plasterka, dołączając dwa plasterki z wyłączeniem tego elementu, np. 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 mówi, że jeśli cel ma wystarczającą pojemność, a następnie, że plaster jest resliced. Mam nadzieję, że "reslicing" jest ciągłą operacją czasu. Mam również nadzieję, że to samo dotyczy łączenia ciągów przy użyciu +.

Answer 1

Wszystko zależy od rzeczywistej implementacji, ale bazuję na standardowym Go, a także gccgo.

plastry

Reslicing oznacza liczbę całkowitą zmianę w struktury (plaster jest struktura z trzech pól: długość, pojemności i wskaźnik do pamięci kopii).

Jeśli plasterek nie ma wystarczającej pojemności, w załączniku należy przydzielić nową pamięć i skopiować starą. Dla plastrów z < 1024 elementów, podwoi pojemność, dla plastrów z> 1024 elementami zwiększy ją o czynnik 1,25.

Struny

Ponieważ ciągi są niezmienne, każdy ciąg konkatenacji z + stworzy nowy ciąg, co oznacza kopiowanie starą. Więc jeśli robisz to N razy w pętli, przydzielisz N ciągów i skopiujesz pamięć około N razy.