Массивы, динамические массивы и строки

Массив — самая скучная структура данных и одновременно самая важная. Хеш-таблица внутри себя — массив. Куча — массив. Дерево отрезков — массив. Буфер сокета — массив. Строка — массив. Если вы понимаете, почему массив быстрый и где именно он перестаёт быть быстрым, вы понимаете большую часть практической производительности структур данных. Статья разбирает три слоя одной идеи «непрерывный блок памяти»: статический массив (адресная арифметика и кэш), динамический массив (политика роста и амортизация) и строку (массив байтов с нетривиальной семантикой «элемента»). Предполагается, что вы прочитали Асимптотику, амортизацию и модель памяти.

1. Массив: почему O(1) — это правда

Интуиция и формула

Представьте склад с ячейками одинакового размера, пронумерованными подряд. Чтобы найти ячейку №5000, кладовщику не нужно проходить мимо 4999 ячеек — он знает шаг и идёт сразу в нужное место. Это и есть массив: однородные элементы, лежащие подряд. Формально, если массив начинается по адресу base, а элемент занимает S байт:

addr(a[i]) = base + i * S

Одно умножение и одно сложение — независимо от i и от длины. Отсюда O(1) на произвольный доступ, причём с крошечной константой: на x86-64 это одна инструкция mov rax, [rdi + rsi*4] — режим адресации base + index*scale умножает бесплатно.

Два условия, без которых формула ломается. Однородность: все элементы одного размера (массив «объектов разного размера» невозможен; в языках со ссылочной семантикой массив объектов — это массив указателей, а сами объекты разбросаны по куче). Непрерывность: блок выделен целиком — именно это даёт кэш-локальность.

Раскладка в памяти и кэш

Асимптотика утверждает, что проход по массиву и по связному списку одинаковы — оба O(n). На практике массив выигрывает в 5–20 раз, и причина не в числе операций, а в иерархии памяти.

Процессор читает память не байтами, а кэш-линиями по 64 байта. Читая a[0], вы бесплатно получаете a[1..15] (для int32). Плюс аппаратный префетчер распознаёт линейный шаблон обращений и подтягивает следующие линии заранее. Порядки задержек (см. Latency Numbers Every Programmer Should Know): L1 ≈ 1 нс, L2 ≈ 4 нс, L3 ≈ 15 нс, DRAM ≈ 80 нс, NVMe ≈ 100 мкс. То есть один промах до DRAM стоит как ~80 попаданий в L1 — сотни тактов простоя.

Практический вывод: асимптотика выбирает алгоритм, локальность выбирает структуру. Между O(n) с последовательным доступом и O(n) с произвольным — разница на порядок.

Раскладка многомерных массивов и AoS против SoA

«Двумерный массив» в памяти всё равно одномерный. В C, C++, Python/NumPy, Go, Rust используется row-major (строки подряд): addr(a[i][j]) = base + (i * ncols + j) * S; в Fortran, MATLAB, R — column-major. Обход матрицы 4096×4096 по строкам и по столбцам делает одинаковое число арифметических операций, но столбцовый вариант медленнее в 3–10 раз: шаг 16 КБ означает новую кэш-линию на каждый элемент и промахи TLB. То же соображение лежит в основе блочного (tiled) умножения матриц — разбиваем на подматрицы, помещающиеся в L1.

Тот же принцип на уровне структур:

// AoS (Array of Structures): удобно, но чтение одного поля тянет в кэш всю структуру.
type Particle struct{ X, Y, Z, VX, VY, VZ, Mass float32 }

// SoA (Structure of Arrays): каждое поле — отдельный плотный массив.
// Проход «обновить только X» читает ровно нужные байты и векторизуется SIMD.
type ParticleSystem struct{ X, Y, Z, VX, VY, VZ, Mass []float32 }

SoA — ровно то, что делают колоночные хранилища: Arrow, Parquet, ClickHouse, DuckDB. Запрос SELECT avg(price) FROM orders в колоночном формате читает один непрерывный массив вместо всех полей всех строк (Apache Arrow Columnar Format).

Стоимость операций и приёмы, возможные только на массиве

Строка «удаление из середины — O(n)» — главная причина существования связных списков. Но если порядок не важен, удаление становится O(1) через swap-remove — идиома игровых движков и ECS:

def swap_remove(a: list, i: int) -> None:
    """O(1) ценой потери порядка."""
    a[i] = a[-1]
    a.pop()


def build_prefix(a: list[int]) -> list[int]:
    """Префиксные суммы: препроцессинг O(n), затем сумма любого отрезка за O(1)."""
    p = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        p[i + 1] = p[i] + x
    return p                       # сумма a[l..r) == p[r] - p[l]

Непрерывность и целочисленная индексация делают возможными два указателя, скользящее окно, разворот на месте (reverse-reverse-reverse из Programming Pearls), бинарный поиск и алгоритм Кадане — техники, недоступные спискам и деревьям. Если массив меняется между запросами, префиксные суммы не годятся: нужны дерево Фенвика или дерево отрезков.

2. Динамический массив: рост и амортизация

Статический массив требует знать размер заранее. Динамический массив (std::vector, ArrayList, list в Python, Vec в Rust, слайс в Go) снимает это ограничение, храня три вещи: указатель на буфер, длину (len) и ёмкость (cap).

Ключевой инвариант: 0 ≤ len ≤ cap. Ячейки [len, cap) выделены, но не инициализированы — в C++ там нет сконструированных объектов, в Go они занулены, в Rust к ним нельзя обратиться без unsafe. Путаница между len и cap — источник целого класса багов.

Алгоритм append

Узел K — не мелочь: перевыделение инвалидирует все указатели, ссылки и итераторы на элементы. В C++ это undefined behaviour, в Go — молчаливо неверные данные, в Rust — ошибка компиляции благодаря borrow checker.

Почему append амортизированно O(1)

Отдельный append может стоить O(n) — когда происходит перевыделение. Но последовательность из n добавлений стоит O(n), то есть в среднем O(1) на операцию. Три стандартных доказательства (CLRS, глава 17):

Метод суммирования. С cap = 1 и коэффициентом 2 перевыделения случаются на добавлениях 1, 2, 3, 5, 9, 17, …, 2^k+1. Суммарное копирование: 1 + 2 + 4 + … + 2^k = 2^(k+1) − 1 < 2n. Плюс n собственно записей → < 3n операций на n добавлений, то есть 3 записи на append амортизированно.

Метод предоплаты. Берём с каждого append «налог» в 3 монеты: 1 — оплатить запись элемента, 2 — отложить на будущее копирование. К следующему перевыделению cap/2 новых элементов внесли по 2 монеты = cap монет — ровно цена копирования cap элементов.

Метод потенциала. Положим Φ = 2·len − cap (неотрицателен при len ≥ cap/2). Дешёвый append: реальная стоимость 1, ΔΦ = 2 → амортизированная 3. Дорогой при len = cap: реальная len + 1, ΔΦ = 2 − cap → амортизированная len + 1 + 2 − cap = 3. Снова 3.

Критично: амортизация работает только при геометрическом росте. Если наращивать ёмкость на константу c, перевыделений будет n/c, суммарное копирование — c + 2c + … + n = Θ(n²/c), то есть Θ(n) на операцию. Это классическая ошибка самописных контейнеров.

Какой коэффициент роста выбрать

Почему не всегда 2? Известный аргумент: при k ≥ 2 сумма всех ранее освобождённых блоков 1 + 2 + … + cap/2 = cap − 1 никогда не покрывает следующий запрос 2·cap, поэтому аллокатор не может переиспользовать освободившееся место; при k < φ ≈ 1.618 сумма предыдущих блоков рано или поздно превышает следующий запрос (folly/FBVector). Современные аллокаторы (jemalloc, tcmalloc, mimalloc) работают по size-классам, и эффект слабее теории, но компромисс «меньше копирований против меньше пикового overhead» реален. Пик памяти при перевыделении — cap + k·cap: при k = 2 вы кратковременно держите три размера данных, для массива в 4 ГБ это 12 ГБ пика. Поэтому reserve / make([]T, 0, n) — не микрооптимизация, а способ не словить OOM.

Реализация с нуля

import ctypes


def alloc(n):
    return (n * ctypes.py_object)()          # аналог malloc(n * sizeof(void*))


class DynamicArray:
    """Инварианты: 0 <= _len <= _cap; ячейки [0, _len) инициализированы,
    [_len, _cap) — выделенный, но не заполненный «мусор»."""

    GROWTH = 2

    def __init__(self, capacity: int = 1):
        self._len, self._cap = 0, max(1, capacity)
        self._buf = alloc(self._cap)

    def __getitem__(self, i: int):           # O(1): адресная арифметика
        if not 0 <= i < self._len:
            raise IndexError("индекс вне диапазона")
        return self._buf[i]

    def _resize(self, new_cap: int) -> None:
        """O(n): выделить, скопировать, отпустить старый буфер."""
        new_buf = alloc(new_cap)
        for i in range(self._len):
            new_buf[i] = self._buf[i]
        self._buf, self._cap = new_buf, new_cap   # старый освободит GC

    def append(self, value) -> None:
        """Амортизированно O(1), в худшем случае O(n)."""
        if self._len == self._cap:
            self._resize(self._cap * self.GROWTH)
        self._buf[self._len] = value
        self._len += 1

    def insert(self, i: int, value) -> None:
        """O(n): сдвигаем хвост вправо, идя справа налево."""
        self.append(value)
        for j in range(self._len - 1, i, -1):
            self._buf[j] = self._buf[j - 1]
        self._buf[i] = value

    def pop(self):
        """O(1) амортизированно; сжимаемся при заполненности ниже 1/4."""
        if self._len == 0:
            raise IndexError("pop из пустого массива")
        self._len -= 1
        value = self._buf[self._len]
        if self._cap > 1 and self._len * 4 <= self._cap:
            self._resize(max(1, self._cap // 2))
        return value

Обратите внимание на условие сжатия: порог 1/4, а ужимаемся до 1/2. Это не случайность. Если сжимать при заполненности ровно 1/2 и до 1/2 ёмкости, последовательность append, pop, append, pop, … на границе вызовет перевыделение на каждой операции — амортизация ломается, стоимость становится Θ(n). Разрыв (гистерезис) между порогом сжатия и целевой заполненностью даёт запас в cap/4 дешёвых операций в любую сторону. То же соображение — при выборе порогов rehash в хеш-таблицах. Кстати, list в CPython при pop() память практически не возвращает — если это важно, пересоздайте список явно.

Слайсы Go: где ломаются интуиции

Go-слайс — «дескриптор» из трёх слов (ptr, len, cap), передаваемый по значению. Отсюда самые популярные ошибки.

base := []int{1, 2, 3, 4, 5}

// ЛОВУШКА 1: подслайс наследует cap до конца исходного буфера.
head := base[:2]                  // len=2, cap=5
head = append(head, 99)           // места хватило → ПЕРЕЗАПИСАЛИ base[2]
fmt.Println(base)                 // [1 2 99 4 5] — исходный слайс испорчен
safe := base[:2:2]                // three-index slice: len=2, cap=2 → append скопирует

// ЛОВУШКА 2: маленький подслайс удерживает огромный буфер от GC.
huge := make([]byte, 100<<20)                   // 100 МБ
prefix := huge[:16]                             // держит все 100 МБ живыми!
detached := append([]byte(nil), huge[:16]...)   // явная копия — решение

// ЛОВУШКА 3: append на копии дескриптора не виден вызывающему.
func grow(s []int) { s = append(s, 42) }        // мутирует локальную копию

// ЛОВУШКА 4: известен финальный размер — резервируйте.
out := make([]int, 0, len(base))                // 0 перевыделений вместо log2(n)

Официальное объяснение модели — Go Slices: usage and internals и The Mechanics of ‘append’. Ловушка №2 — реальная причина не одного инцидента: хендлер парсит 10 МБ тела, кладёт из него 20-байтовый ID в кэш, и кэш на 100 тысяч записей внезапно держит гигабайты.

3. Строки: массив байтов, притворяющийся массивом символов

Строка — динамический массив, у которого «элемент» определён неоднозначно. Эта неоднозначность порождает большинство строковых багов.

Байты лежат в памяти и летят по сети. Code point — номер символа в Unicode, от U+0000 до U+10FFFF. Графемный кластер — то, что пользователь считает одним символом: буква с диакритикой, эмодзи с модификатором тона кожи, семья из четырёх эмодзи, склеенных ZWJ (UAX #29). Правило: len() в любом языке отвечает на вопрос одного из этих уровней и почти никогда — на тот, который вы имели в виду.

Отсюда аномалия JS/Java: "𝄞".length === 2, потому что скрипичный ключ U+1D11E вне BMP и кодируется суррогатной парой. А в Python len("👨‍👩‍👧‍👦") == 7 — четыре эмодзи и три ZWJ, хотя на экране один значок.

Неизменяемость и квадратичная конкатенация

В Java, Python, Go, C#, JS строки неизменяемы. Плюсы: безопасное разделение буфера, кэшируемый хеш, потокобезопасность без синхронизации, интернирование. Минус ровно один, но болезненный:

def join_bad(parts: list[str]) -> str:
    result = ""
    for p in parts:
        result += p        # ПЛОХО: O(n^2) — новая строка и копия префикса на каждом шаге
    return result

def join_good(parts: list[str]) -> str:
    return "".join(parts)  # ХОРОШО: O(n) — проход на подсчёт длины, проход на копирование

Это «Schlemiel the Painter’s algorithm»: маляр красит дорогу, но каждый раз возвращается к банке с краской в начале. 100 000 конкатенаций по 100 байт — это ~500 МБ копирования вместо 10 МБ. (CPython содержит оптимизацию с realloc на месте при refcount == 1, из-за которой наивный бенчмарк += иногда выглядит линейным; это деталь реализации, не гарантия языка, и в PyPy её нет.)

Правильный инструмент — изменяемый буфер, то есть наш DynamicArray<char>: StringBuilder в Java и C#, strings.Builder в Go, String::push_str в Rust. И в каждом из них не забывайте про резервирование — это тот же reserve:

var sb strings.Builder
sb.Grow(expectedSize)                 // reserve: 0 перевыделений вместо log2(n)
for _, p := range parts {
    sb.WriteString(p)
}
result := sb.String()                 // конверсия без копирования буфера

Эволюция строковых представлений

История с Java 7u6 поучительна. До неё substring возвращал объект, разделяющий тот же char[] — O(1). Побочный эффект: вырезав 10 символов из мегабайтного лога и положив их в долгоживущую мапу, вы удерживали весь мегабайт (та же ловушка №2 из Go-слайсов). Oracle сменил O(1)-шаринг на O(n)-копирование, сознательно ухудшив асимптотику ради предсказуемости памяти — JDK-4513622. Отличная иллюстрация: асимптотика — не единственный критерий проектирования.

Работа с UTF-8 на практике

s := "Привет, мир! 🏁"

fmt.Println(len(s))                      // 25 — БАЙТ, не символов
fmt.Println(utf8.RuneCountInString(s))   // 14 — code points

for i, r := range s {                    // range декодирует UTF-8:
    fmt.Printf("%d: %c\n", i, r)         // i — байтовый индекс, r — руна
}

_ = s[0]                                 // ОПАСНО: это байт 0xD0, а не буква 'П'
// s[:6] может разрезать многобайтовую последовательность → невалидный UTF-8 и U+FFFD

runes := []rune(s)                       // O(n) аллокация, зато индексация по code points
fmt.Println(string(runes[:6]))           // "Привет"

Ключевая мысль: произвольный доступ по «символу» в UTF-8 стоит O(n), а не O(1) — строка перестаёт быть массивом в строгом смысле. UTF-8 сознательно жертвует индексацией ради компактности, самосинхронизации (по любому байту видно, начало это или продолжение) и совместимости с ASCII — см. UTF-8 history, Rob Pike. Нужна индексация по символам в горячем цикле — конвертируйте один раз в массив рун.

Сравнение строк «как видит человек» требует нормализации Unicode (NFC/NFD): "é" как U+00E9 и как "e" + U+0301 — разные байты, одинаковый текст. Регулярный источник багов в поиске, дедупликации и логине (UAX #15).

Оптимизации, о которых стоит знать

• SSO (Small String Optimization). std::string в libstdc++/libc++ хранит строки до 15–22 байт внутри самого объекта, без обращения к куче: профиль аллокаций резко меняется на границе размера.
• Интернирование и Compact Strings. Java держит литералы в пуле (O(1) сравнение по ссылке ценой глобальной хеш-таблицы) и с версии 9 хранит byte[] плюс однобайтовый coder: latin-1, если все символы влезают, иначе UTF-16 — 5–10% экономии кучи (JEP 254).
• Rope / gap buffer / piece table. Редакторы (Emacs, VS Code, Xi) не используют плоский массив: вставка в середину 100-мегабайтного файла за O(n) неприемлема. Rope — сбалансированное дерево фрагментов, вставка O(log n).
• Поиск подстроки. Наивный — O(nm); KMP, Бойер—Мур, Рабин—Карп сводят к O(n + m). Структуры для множественных запросов — в статье Префиксные деревья и строковые структуры.

4. Типичные ошибки

1. Линейный рост вместо геометрического в самописном контейнере → O(n²) вместо O(n).
2. Конкатенация строк в цикле вместо join / StringBuilder → тот же квадрат.
3. Удержание указателей после append/push_back. В C++ — UB, в Go — тихая порча данных. Правило: после любой операции, способной перевыделить буфер, все ссылки мертвы.
4. Удаление из середины прямо в цикле без учёта сдвига индексов:

   for i, x in enumerate(items):   # НЕЛЬЗЯ: мутация во время итерации
       if bad(x):
           items.pop(i)            # пропускает следующий элемент
   items = [x for x in items if not bad(x)]   # правильно, O(n)
   

5. Подслайс или подстрока держит гигантский буфер → «утечка», не видимая в профайлере объектов. Делайте явную копию перед долгим хранением.
6. len() строки как число символов. Правило «пароль не короче 8 символов» на UTF-16 code units ломается на эмодзи; обрезка «первые 100 символов» рвёт графемные кластеры.
7. Забыть reserve, когда финальный размер известен: лишние log₂(n) перевыделений и до 3× пикового потребления памяти.
8. Сжатие при том же пороге, что и рост → thrashing, амортизация разрушена.
9. Обход двумерного массива не в порядке раскладки → кратное замедление без изменения асимптотики.
10. Сравнение строк без нормализации Unicode при работе с пользовательским вводом.

5. Как это применяют в проде

• Колоночные СУБД и Arrow. ClickHouse, DuckDB, Parquet хранят колонки плотными массивами и обрабатывают батчами по несколько тысяч значений, чтобы данные помещались в L2 и работала SIMD-векторизация. Порядок ускорения аналитических запросов относительно построчного формата. Подробнее — трек Data Engineering.
• Ring buffer поверх массива. Очереди Kafka-типа, аудио- и сетевые буферы, io_uring — фиксированный массив плюс два индекса по модулю, без аллокаций в горячем пути. См. Стеки, очереди и деки.
• Хеш-таблицы с открытой адресацией. Swiss Tables (Abseil, Rust hashbrown, Go 1.24+) строятся на плотных массивах и SIMD-сканировании 16 байт метаданных за инструкцию — прямое следствие кэш-локальности. См. Хеш-таблицы.
• Неявные структуры в массиве. Бинарная куча живёт в массиве без единого указателя: дети узла i — это 2i+1 и 2i+2. Дерево отрезков — тоже массив. См. Кучи и Дерево отрезков.
• Arena-аллокаторы и zero-copy парсинг. Один большой массив объектов плюс индексы вместо указателей (u32 против 8 байт: вдвое меньше памяти, дружественнее к GC и сериализации) — стандартный приём в компиляторах и ECS. А []byte-слайсы поверх буфера запроса вместо строк — основа быстрых парсеров (fasthttp, simdjson); цена — ровно та ловушка удержания буфера, поэтому такие API явно оговаривают время жизни данных.

Мини-итог

• Массив быстрый не потому, что O(1), а потому что непрерывный: адресная арифметика плюс кэш-линии и префетч.
• Динамический массив = массив + политика роста. Геометрический рост даёт амортизированный O(1) для append; линейный — не даёт. Коэффициент (1.5 против 2) — компромисс между числом копирований и пиковым потреблением памяти.
• Перевыделение инвалидирует все ссылки на элементы. Это причина багов во всех языках, где компилятор этого не запрещает.
• reserve / Grow / make(..., 0, n) — самая дешёвая оптимизация в вашем арсенале.
• Строка — динамический массив байтов с неоднозначным «элементом»: байты ≠ code points ≠ графемные кластеры. Индексация по символу в UTF-8 — O(n).
• Неизменяемость строк даёт безопасность и превращает наивную конкатенацию в цикле в квадратичный алгоритм. Ответ — изменяемый буфер: join, StringBuilder, strings.Builder.

Источники

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 4-е изд. — глава 17 «Amortized Analysis», глава 10 «Elementary Data Structures». Sedgewick, Wayne. Algorithms, 4th ed. — resizing arrays. Bentley. Programming Pearls, 2nd ed.
• Drepper. What Every Programmer Should Know About Memory — лучший разбор кэшей и иерархии памяти.
• PEP 393, JEP 254: Compact Strings, CPython listobject.c — формула роста в list_resize.
• Joel Spolsky. The Absolute Minimum Every Software Developer Must Know About Unicode.

Что дальше

Мы разобрали структуру, где доступ по индексу дешёвый, а вставка в середину дорогая. Логичный следующий вопрос — можно ли поменять эти цены местами: платить O(1) за вставку, отказавшись от индексации и кэш-локальности. Именно этим занимаются Связные списки: односвязные, двусвязные, кольцевые — и там же мы честно разберём, почему в реальном коде они встречаются гораздо реже, чем обещают учебники.