Каков механизм использования добавления к добавлению в Go?

Предположим, что у меня есть срез slice типа int. При объявлении я установил третий аргумент в size, который, как я полагаю, сохраняет память по крайней мере для size ints, задав параметр cap среза.

slice:=make([]int,0,size)
Теперь предположим, что у меня есть целочисленная переменная value. Чтобы добавить его к срезу в конце, я использую 
slice=append(slice,value)

Если число элементов, находящихся в данный момент в срезе, меньше size, то не будет необходимости копировать весь базовый массив в новое место, чтобы добавьте новый элемент.

Далее, если я хочу добавить value к slice, как предложено здесь и здесь, я использую 

slice=append([]int{value},slice...)
Мой вопрос в том, что происходит в этом случае? Если число элементов все еще меньше size, то как элементы хранятся в памяти? Предполагая непрерывное распределение при вызове функции make(), все ли существующие элементы смещены вправо, чтобы освободить первое пространство для значения? Или перераспределяется память и все элементы скопировал? Причина вопроса в том, что я хотел бы, чтобы моя программа была как можно быстрее, и хотел бы знать, является ли это возможной причиной для замедления ее работы. Если это так, есть ли какой-либо альтернативный способ подготовки, который был бы более эффективным во времени?
2 4
slice memory-management prepend

2 ответа:

С реслицированием и копированием

Встроенный append() всегда добавляет элементы в срез. Вы не можете использовать его (в одиночку)для добавления элементов.

Сказав, что, если у вас есть срез вместимостью больше длины (имеет "свободное" пространство после его элементов), к которому вы хотите добавить элемент, вы можете повторно добавить исходный срез, скопировать все элементы в индекс на один выше, чтобы освободить место для нового элемента, а затем установить элемент в 0 - й индекс. Этот не потребуется никаких новых ассигнований. Вот как это могло бы выглядеть: 

func prepend(dest []int, value int) []int {
    if cap(dest) > len(dest) {
        dest = dest[:len(dest)+1]
        copy(dest[1:], dest)
        dest[0] = value
        return dest
    }

    // No room, new slice need to be allocated:
    // Use some extra space for future:
    res := make([]int, len(dest)+1, len(dest)+5)
    res[0] = value
    copy(res[1:], dest)
    return res
}

Тестирование: 

s := make([]int, 0, 5)
s = append(s, 1, 2, 3, 4)
fmt.Println(s)
s = prepend(s, 9)
fmt.Println(s)
s = prepend(s, 8)
fmt.Println(s)

Вывод (попробуйте на Go Playground):

[1 2 3 4]
[9 1 2 3 4]
[8 9 1 2 3 4]

Примечание: если нет места для нового элемента, так как производительность имеет значение сейчас, мы не просто сделали: 

res := append([]int{value}, dest...)

Потому что он выделяет и копирует больше, чем нужно: выделяет срез для литерала ([]int{value}), а затем append() выделяет новый при добавлении к нему dest.

Вместо этого наше решение выделяет только один новый массив (по make(), даже зарезервировав некоторое пространство для будущего роста), затем просто установите value в качестве первого элемента и скопируйте dest (предыдущие элементы).

Со связанным списком

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

Стандартная библиотека обеспечивает общую реализацию в container/list пакет.

С ручным управлением большим резервным массивом

Придерживаясь нормальных срезов и массивов, есть еще одно решение.

Если вы хотите управлять большим резервным массивом (или срезом) самостоятельно, вы можете сделать это, оставив свободное пространство перед срезом, который вы используете. При предварительном вводе можно создать новое значение среза из резервной копии более крупный массив или срез, который начинается с индекса, оставляющего место для 1 элемента, подлежащего добавлению.

Без полноты, просто для демонстрации: 

var backing = make([]int, 15) // 15 elements
var start int

func prepend(dest []int, value int) []int {
    if start == 0 {
        // No more room for new value, must allocate bigger backing array:
        newbacking := make([]int, len(backing)+5)
        start = 5
        copy(newbacking[5:], backing)
        backing = newbacking
    }

    start--
    dest = backing[start : start+len(dest)+1]
    dest[0] = value
    return dest
}

Тестирование / использование: 

start = 5
s := backing[start:start] // empty slice, starting at idx=5
s = append(s, 1, 2, 3, 4)
fmt.Println(s)
s = prepend(s, 9)
fmt.Println(s)
s = prepend(s, 8)
fmt.Println(s)

// Prepend more to test reallocation:
for i := 10; i < 15; i++ {
    s = prepend(s, i)
}
fmt.Println(s)

Вывод (попробуйте на Go Playground):

[1 2 3 4]
[9 1 2 3 4]
[8 9 1 2 3 4]
[14 13 12 11 10 8 9 1 2 3 4]

Анализ: это решение не выделяет и не копирует, когда есть место в срезе backing, чтобы добавить значение! все, что происходит, - это создание нового среза из среза backing, который покрывает destination + 1 пробел для добавляемого значения, устанавливает его и возвращает это значение среза. Ты не можешь стать лучше, чем сейчас.

Если нет места, то он выделяет больший кусок backing, копирует содержимое старого, а затем делает "нормальное" предписание.

С использованием хитрого ломтика

Идея: представьте, что вы всегда храните элементы в срезе в обратном порядке.

Хранение элементов в обратном порядке в срезе означает, что предписание становится добавить!

Таким образом, чтобы" подготовить " элемент, вы можете просто использовать append(s, value). И это все.

Да, это имеет свои ограниченные применения (например, добавление к срезу, хранящемуся в обратном порядке, имеет те же проблемы и сложность, что и "обычный" срез и операция предварительной обработки), и вы теряете много удобств (возможность перечислять элементы с помощью for range только для того, чтобы назвать один), но с точки зрения производительности ничто не сравнится с предварительной обработкой значения просто с помощью append().

Примечание: итерация по элементам, которые хранит элементы в обратном порядке должны использовать нисходящий цикл, например: 

for i := len(s) - 1; i >= 0; i-- {
    // do something with s[i]
}

Заключительное Примечание: все эти решения могут быть легко расширены, чтобы добавить срез вместо простого значения. Обычно дополнительное пространство при повторном вызове - это не +1, а +len(values), и не просто установка dst[0] = value, а вызов copy(dst, values).

4

Вызов "prepend" должен выделить массив и скопировать все элементы, потому что срез в Go определяется как начальная точка, размер и распределение (с учетом распределения от начальной точки).

Срез никак не может знать, что элемент перед первым может быть использован для расширения среза.

Что будет с 

slice = append([]int{value}, slice...)

Есть

  1. выделяется новый массив из одного элемента value (вероятно, на стек)
  2. для отображения этого элемента создается срез (start=0, size=1, alloc=1)
  3. вызов append выполнен
  4. append видит, что не хватает места для расширения одноэлементного среза, поэтому выделяет новый массив и копирует все элементы
  5. для ссылки на этот массив создается новый объект slice

Если добавление/удаление на обоих концах большого контейнера является обычным случаем использования для вашего приложения, то вам нужен контейнер deque. Это к сожалению, недоступно в Go и невозможно эффективно писать для универсальных содержащихся типов при сохранении удобства использования (потому что Go все еще не хватает универсальных типов).

Однако вы можете реализовать deque для вашего конкретного случая, и это легко (например, если у вас есть большой контейнер с известной верхней границей, может быть круговой буфер - это все, что вам нужно, и это всего лишь пара строк кода).

Я очень Новичок, чтобы идти, так что может быть следующее очень плохо идти код... но это попытка реализовать deque с помощью растущего кругового буфера (в зависимости от случая использования это может быть или не быть хорошим решением) 

type Deque struct {
    buffer  []interface{}
    f, b, n int
}

func (d *Deque) resize() {
    new_buffer := make([]interface{}, 2*(1+d.n))
    j := d.f
    for i := 0; i < d.n; i++ {
        new_buffer[i] = d.buffer[j]
        d.buffer[j] = nil
        j++
        if j == len(d.buffer) {
            j = 0
        }
    }
    d.f = 0
    d.b = d.n
    d.buffer = new_buffer
}

func (d *Deque) push_back(x interface{}) {
    if d.n == len(d.buffer) {
        d.resize()
    }
    d.buffer[d.b] = x
    d.b++
    if d.b == len(d.buffer) {
        d.b = 0
    }
    d.n++
}

func (d *Deque) push_front(x interface{}) {
    if d.n == len(d.buffer) {
        d.resize()
    }
    if d.f == 0 {
        d.f = len(d.buffer)
    }
    d.f--
    d.buffer[d.f] = x
    d.n++
}

func (d *Deque) pop_back() interface{} {
    if d.n == 0 {
        panic("Cannot pop from an empty deque")
    }
    if d.b == 0 {
        d.b = len(d.buffer)
    }
    d.b--
    x := d.buffer[d.b]
    d.buffer[d.b] = nil
    d.n--
    return x
}

func (d *Deque) pop_front() interface{} {
    if d.n == 0 {
        panic("Cannot pop from an empty deque")
    }
    x := d.buffer[d.f]
    d.buffer[d.f] = nil
    d.f++
    if d.f == len(d.buffer) {
        d.f = 0
    }
    d.n--
    return x
}
3