Какова вычислительная сложность операции добавления элемента в конец слайса (slice) в Go?

Добавление элемента в конец слайса с помощью встроенной функции append имеет амортизированную постоянную сложность O(1).

Давайте разберемся, почему так.

Внутреннее устройство слайса

Слайс — это структура-заголовок, которая содержит три поля:

1. Указатель на начало нижележащего массива (underlying array).
2. Длина (len) — количество элементов в слайсе.
3. Емкость (cap) — количество элементов, которое может вместить нижележащий массив, начиная с указателя.

Два сценария при вызове append

1. Когда len < cap (в массиве есть свободное место):

   • Сложность: O(1).
   • Происходит следующее: новый элемент просто добавляется в следующую свободную ячейку нижележащего массива, и len слайса увеличивается на 1. Это очень быстрая операция.

2. Когда len == cap (свободного места нет):

   • Сложность: O(n), где n — текущий размер слайса.
   • Происходит дорогостоящая операция переаллокации:
     1. Выделяется память под новый, больший массив.
     2. Все элементы из старого массива копируются в новый.
     3. Новый элемент добавляется в конец нового массива.
     4. Заголовок слайса обновляется: указатель теперь ведет на новый массив, а len и cap обновляются.

Почему сложность амортизированная O(1)?

Хотя операция переаллокации имеет сложность O(n), она происходит нечасто. Go использует стратегию роста с запасом: при переаллокации capacity нового массива становится значительно больше, чем len.

• Стратегия роста: До Go 1.18 для слайсов размером до 1024 элементов capacity удваивалась (new_cap = 2 * old_cap). Для больших слайсов она росла медленнее (примерно на 25%). В новых версиях Go алгоритм может быть более сложным, но общий принцип сохраняется.

Благодаря такому экспоненциальному росту, стоимость дорогой операции O(n) «размазывается» по множеству предшествующих ей дешевых операций O(1). В среднем, стоимость добавления одного элемента остается постоянной.

Практический совет

Если вы заранее знаете примерное количество элементов, которое будет храниться в слайсе, создавайте его с нужной capacity, чтобы избежать переаллокаций и связанных с ними накладных расходов.

// Создаем слайс с длиной 0, но с емкостью 1000.
// Все последующие 1000 вызовов append будут иметь сложность O(1).
s := make([]int, 0, 1000)

for i := 0; i < 1000; i++ {
    s = append(s, i) // Нет переаллокаций
}