Сложность `append`

Ответ 1

Спецификация языка программирования 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 исходный файл

Массивы, срезы (и строки): Механика 'append'

Ответ 2

Он не перераспределяется при каждом добавлении, и он явно определен в docs:

Если емкость s недостаточно велика, чтобы соответствовать дополнительным значениям, добавьте выделение нового достаточно большого фрагмента, который соответствует как существующим элементам среза, так и дополнительным значениям. Таким образом, возвращенный фрагмент может ссылаться на другой базовый массив.

Амортизированное постоянное время, таким образом, требует сложности.