Что такое массив, если смотреть на байты

В учебниках массив рисуют как ряд клеточек. Это не метафора — в памяти он именно так и лежит. Массив — это непрерывный блок байтов, разделённый на ячейки одного и того же размера. И этот размер известен заранее. Из этих двух свойств вытекает вся «магия» массива: O(1) доступ по индексу, контролируемая cache locality, предсказуемый размер.

Возьмём C-массив int32_t xs[5] = {10, 20, 30, 40, 50}. Каждый int32_t занимает 4 байта. Если массив начинается с адреса 0x1000, то в памяти лежит:

База — 0x1000. Чтобы получить xs[3], процессору не надо ничего искать: он вычисляет 0x1000 + 3 * 4 = 0x100C и читает 4 байта по этому адресу. Это одна операция — сложение и умножение на константу. И именно эту операцию мы называем O(1) random access.

Формула адреса

Главная формула массива простая:

address(xs[i]) = base + i * sizeof(element)

• base — адрес первого элемента. Знаем при выделении массива.
• i — индекс. Параметр, который вы передаёте.
• sizeof(element) — фиксированный размер ячейки. Знаем по типу: int32_t = 4, int64_t = 8, double = 8.

Чтобы это работало, нужно три вещи:

1. Элементы лежат подряд. Никаких дырок, никаких пропусков. Иначе формула врёт.
2. Все элементы одного размера. Иначе непонятно, на что умножать i.
3. База известна. Это указатель, который хранит сама переменная-массив.

Если хоть одно условие нарушено — это уже не массив (в классическом смысле). Например, Python list хранит указатели на объекты, и у каждого объекта свой размер. Сам массив указателей — да, удовлетворяет условиям, и доступ по индексу там O(1). А вот сами значения лежат где-то по разным адресам. Об этом подробно — в следующем уроке.

Почему это O(1)

«O(1)» — значит время доступа не зависит от размера массива. Прочитать xs[0] стоит столько же, сколько xs[999_999_999] в массиве на миллиард элементов. Процессор делает одно и то же:

1. Берёт базу из регистра (1 такт).
2. Умножает индекс на размер элемента (1 такт; для степеней двойки — сдвиг).
3. Складывает (1 такт).
4. Читает память по адресу (от ~4 тактов до ~300, зависит от кэша).

Время чтения может варьироваться из-за кэшей и страничной памяти — но это уже не алгоритмическая сложность, это микро-архитектура. Алгоритм здесь действительно константный.

Сравнение с другими структурами

Когда мы говорим «массив O(1)», мы подчёркиваем разницу с другими структурами:

В связном списке нет формулы адреса — есть только указатель на следующий узел. Чтобы попасть на 3-й, нужно сделать 3 прыжка. Подробнее об этом — в модуле «Связные списки».

Размер и фиксация типа

Из формулы есть прямое следствие: классический массив типизирован. В одном массиве int32_t xs[N] нельзя хранить разные типы. Сам процессор не различает, где int32_t, а где float: для него массив — это байты. Тип знает компилятор: он определяет, по сколько байт за раз читать и как их интерпретировать.

В Python мы привыкли, что в list можно класть что угодно — int, str, dict в одном списке. Это возможно потому, что list хранит указатели на объекты, а указатель всегда фиксированного размера (8 байт на 64-битной системе). Сами объекты живут отдельно. Это «массив указателей» — и мы разберём его в следующем уроке.

Истинные типизированные массивы в Python есть:

• array.array('i', [1,2,3]) — массив int фиксированного размера, как в C.
• numpy.ndarray(dtype=int32) — то же, плюс batch-операции и broadcasting.
• bytes и bytearray — массивы байт (unsigned char).

С точки зрения памяти эти структуры выглядят как «настоящие» массивы из учебника.

Зачем это знать junior DE

Каждый раз, когда вы видите «O(1) индексация», за этим стоит арифметика адресов. Это объясняет:

• Почему xs[i] быстро даже на больших данных.
• Почему массивы C/Rust/Go быстрее Python list — нет лишнего разыменования.
• Почему numpy умеет SIMD-операции: данные подряд, можно загрузить 4 (или 8, 16) элементов в SIMD-регистр одной командой.
• Почему массивы — основа всего: deque, ring buffer, hash table, B-tree все строятся поверх массивов.

И почему массив плохо растёт: добавление элемента в середину требует сдвига всех последующих. Об этом — в модуле «Динамические массивы».

Попробуй сам

В Python нет «чистого» C-массива в стандартной библиотеке, но есть array.array, который ближе всего:

import array

xs = array.array('i', [10, 20, 30, 40, 50])

# доступ по индексу — O(1), просто арифметика адресов
print(xs[0])     # 10
print(xs[3])     # 40

# можно посмотреть на адрес буфера и размер ячейки
addr, length = xs.buffer_info()
print(f"base address: 0x{addr:x}")
print(f"length:       {length}")
print(f"itemsize:     {xs.itemsize}")   # 4 байта для 'i' (int32)

# адрес i-го элемента, если бы мы писали на C:
i = 3
print(f"address of xs[{i}] = 0x{addr + i * xs.itemsize:x}")

Запустите, посмотрите, что xs.itemsize == 4 — тот самый sizeof(int32_t). И что разница между адресами двух соседних элементов ровно itemsize байт. Никакой магии — арифметика.