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

С нарезкой и копированием

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

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

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, который покрывает место назначения +1. для значения, которое должно быть добавлено, устанавливает его и возвращает это значение среза. Вы не можете стать лучше, чем это.

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

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

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

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

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

Да, у этого есть свои ограничения (например, добавление к срезу, хранящемуся в обратном порядке, имеет те же проблемы и сложность, что и «обычный» срез и операция prepan), и вы теряете многие удобства (возможность перечислять элементы, используя 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).

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

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

Что будет с

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

is

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

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

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

Я очень новичок в Go, поэтому следующий код может быть очень плохим... но это попытка реализовать 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
}