Какова вычислительная сложность этого цикла на языке программирования Go?
var a []int
for i := 0 ; i < n ; i++ {
a = append(a, i)
}
Работает ли append в линейном времени (перераспределение памяти и копирование всего на каждом добавлении) или в постоянное время амортизации (например, как реализуются векторные классы на многих языках)?
Спецификация языка программирования Go говорит, что встроенная функция append перераспределяется при необходимости.
Добавление и копирование фрагментов
Если емкость s не достаточно велика, чтобы соответствовать дополнительным значениям, append выделяет новый, достаточно большой срез, который подходит как для существующие элементы среза и дополнительные значения. Таким образом, возвращенный slice может ссылаться на другой базовый массив.
Точный алгоритм для увеличения целевого среза, когда это необходимо, для добавления зависит от реализации. Для текущего алгоритма компилятора gc см. Функцию growslice в исходном файле Go runtime slice.go. Он амортизировал постоянное время.
В части вычисления вычисления количества в выражении:
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
}
}
}
ДОПОЛНЕНИЕ
Go Language Language Specification позволяет разработчикам языка реализовать встроенную функцию append несколькими способами.
Например, новые распределения должны быть "достаточно большими". Выделенная сумма может быть parsimonius, выделяя минимально необходимую сумму или щедро, выделяя больше минимально необходимой суммы, чтобы свести к минимуму стоимость изменения размера во много раз. Компилятор Go gc использует алгоритм с широким распределением динамического массива с постоянным временем.
Следующий код иллюстрирует две законные реализации встроенной функции append. Щедрая константная функция реализует один и тот же арифметический алгоритм постоянного времени, что и компилятор Go gc. Функция переменной parsimonius после заполнения начального распределения перераспределяет и копирует все каждый раз. В качестве элементов управления используются функция Go append и компилятор Go gccgo.
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))
}
Вывод:
дс:
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
Подводя итог, в зависимости от реализации, как только начальная емкость заполняется, встроенная функция append может или не может перераспределяться при каждом вызове.
Литература:
Добавление и копирование фрагментов
Если емкость s не достаточно велика, чтобы соответствовать дополнительным значениям,
appendвыделяет новый, достаточно большой срез, который подходит как для существующие элементы среза и дополнительные значения. Таким образом, возвращенный slice может ссылаться на другой базовый массив.Добавить в обсуждение спецификации фрагмента
В спецификации (на конце и 1.0.3) указано:
"Если емкость s недостаточно велика, чтобы соответствовать дополнительным значения
appendвыделяет новый, достаточно большой срез, который подходит как существующие элементы среза, так и дополнительные значения. Таким образом возвращенный фрагмент может ссылаться на другой базовый массив."Должно ли это быть "если и только если"? Например, если я знаю емкость моего ломтика достаточно длинная, я уверен, что буду не изменять базовый массив?
Да, вы так уверены.
runtime slice.go исходный файл
Он не перераспределяется при каждом добавлении, и он явно определен в docs:
Если емкость s недостаточно велика, чтобы соответствовать дополнительным значениям, добавьте выделение нового достаточно большого фрагмента, который соответствует как существующим элементам среза, так и дополнительным значениям. Таким образом, возвращенный фрагмент может ссылаться на другой базовый массив.
Амортизированное постоянное время, таким образом, требует сложности.