Базовый CS с нуля

Индексы и смещения

Суть Достижение arr[i] быстро, потому что адрес элемента i — это один арифметический шаг: base_address + i x element_size. arr[0] — первый элемент, потому что его смещение равно нулю. Любой элемент — в одном умножении и одном сложении от тебя — за константное время.

◷ 20 min

Теперь ты знаешь, что массив — это один непрерывный блок ячеек одинакового размера. Но когда ты пишешь scores[3], как программа находит элемент 3? Она не ищет. Она не идёт от начала, считая ячейки одну за другой. Она вычисляет точный адрес элемента 3 за один арифметический шаг и читает прямо оттуда.

Этот один шаг — вся причина, почему массивы повсюду в программировании. Он объясняет, почему arr[3] и arr[3000] занимают ровно одинаковое время, и объясняет факт, который озадачивает каждого новичка: почему первый элемент — это arr[0], а не arr[1].

Этот урок раскрывает эту арифметику. После него синтаксис скобок перестанет быть магией — он станет формулой, которую ты можешь вычислить вручную.

Цель

После этого урока ты сможешь определить индекс и смещение элемента массива, сформулировать формулу, которая превращает индекс в адрес памяти, объяснить, почему элемент 0 — первый элемент, и объяснить, почему достижение любого элемента занимает одинаковое константное время.

Базовый адрес. Из предыдущего урока: массив — это один непрерывный блок, а имя массива ссылается на то, где этот блок начинается. У этого начального адреса есть имя: базовый адрес массива. Это байтовый адрес самой первой ячейки массива.

Адрес каждого другого элемента будет измеряться относительно базового адреса. Базовый адрес — это фиксированная точка опоры; всё остальное вычисляется от неё. Программа знает базовый адрес, как только массив существует, — найти его ничего не стоит.

Индекс и смещение. Индекс элемента — это его позиция, отсчитанная от начала массива: у первого элемента индекс 0, у следующего — 1, затем 2, и так далее. Индекс — это число, которое ты пишешь внутри скобок: arr[2] означает «элемент с индексом 2».

Смещение элемента — это сколько байтов за базовым адресом начинается ячейка этого элемента. Индекс считает элементы; смещение считает байты. Они связаны размером элемента:

смещение = индекс x размер_элемента

Если каждый элемент 4 байта, то у индекса 0 смещение 0, у индекса 1 смещение 4, у индекса 2 смещение 8, и так далее. Смещение индекса i — это просто i размеров элемента в байтах.

Формула адреса. Реальный адрес элемента в памяти — это базовый адрес плюс его смещение. Соединяя две части:

адрес элемента i = base_address + (i x element_size)

Эта одна строка — то, как работает arr[i]. Чтобы прочитать arr[i], программа: берёт базовый адрес (уже известный), умножает индекс i на размер элемента, прибавляет это смещение к базовому адресу и читает ячейку по полученному адресу. Одно умножение, одно сложение, одно чтение.

Заметь, чего нет в формуле: длины массива и каких-либо других элементов. Адрес элемента i зависит только от базового адреса, индекса и размера элемента. Неважно, у массива 10 элементов или 10 миллионов.

Почему первый элемент — индекс 0. Теперь загадка «ошибки на единицу» растворяется. Индекс — это не счёт «который элемент» в обыденном смысле, это смещение, измеренное в элементах, от начала блока.

Первый элемент лежит точно на базовом адресе. Он на ноль элементов за началом. Его смещение — 0 x element_size = 0. Поэтому его адрес — base_address + 0 = base_address. Индекс, который даёт смещение ноль, — это 0, поэтому первый элемент — это arr[0]. Индекс 0 — не причуда синтаксиса; это единственный индекс, чьё смещение равно нулю, а первый элемент — единственный элемент с нулевым смещением. Нумерация навязана арифметикой.

Доступ за константное время. Поскольку адрес любого элемента находится одной и той же фиксированной работой — одно умножение, одно сложение, одно чтение — достижение arr[0] стоит ровно столько же, сколько достижение arr[9999]. Объём работы не растёт с индексом и не растёт с размером массива.

Работа, которая занимает одинаковый фиксированный объём независимо от размера входа, называется константным временем. Индексация массива — классический пример. Это важнейшее свойство массивов: любой элемент, где бы он ни лежал, — в одном арифметическом шаге от тебя.

Почему это работает

Почему это возможно только потому, что массив непрерывен и одинакового размера? Формула base + i x element_size работает только если ячейки однородны и без разрывов. Если бы элементы были разного размера, нельзя было бы умножить индекс на один размер элемента — пришлось бы складывать размеры всех более ранних элементов один за другим, а это уже не константное время. Будь там разрывы, умножение попало бы на неверный адрес. Два свойства массива из предыдущего урока — одинаковый размер и непрерывность — это ровно то, что делает формулу константного времени верной.

Массив из 5 чисел, базовый адрес 1000, размер элемента 4 байта. Индекс под каждой ячейкой считает элементы от 0. Чтобы достичь индекса 3 (выделен): адрес = 1000 + 3 x 4 = 1012. Индекс 0 лежит на смещении 0, точно на базовом адресе, — поэтому он первый элемент.

Разбор примера

Вычисление адреса scores[3].

У массива scores базовый адрес 1000. Каждый элемент — число, занимающее 4 байта. Нам нужен адрес scores[3].

Шаг 1 — Определить части.

base_address = 1000
индекс i = 3
element_size = 4 байта

Шаг 2 — Вычислить смещение. Смещение — это индекс, умноженный на размер элемента: смещение = 3 × 4 = 12 байтов. Элемент 3 начинается на 12 байтов за началом блока.

Шаг 3 — Вычислить адрес. Адрес — это база плюс смещение: адрес = 1000 + 12 = 1012. Ячейка для scores[3] начинается с адреса 1012.

Шаг 4 — Прочитать. Программа читает значение, хранимое по адресу 1012. Готово.

Теперь проверь scores[0]: смещение = 0 × 4 = 0, адрес = 1000 + 0 = 1000 — точно базовый адрес. Первый элемент лежит прямо в начале, поэтому его индекс 0. И проверь scores[4]: смещение = 4 × 4 = 16, адрес = 1016. Каждое из этих вычислений заняло одно и то же одно умножение и одно сложение — это и есть доступ за константное время.

Частая ошибка

Распространённая ошибка — думать, что программа «идёт» к arr[i], шагая по элементам 0, 1, 2, … до i. Это не так. Ходьба сделала бы arr[5000] намного медленнее, чем arr[5]. Программа прыгает прямо к адресу по формуле. Индекс — это не число шагов, которые нужно пройти, это вход в одноразовое вычисление адреса.

Практика 0 / 5

У массива базовый адрес 1000 и размер элемента 4 байта. Используя адрес = база + индекс x размер_элемента, каков адрес элемента 2?

У массива базовый адрес 500 и размер элемента 8 байтов. Каков адрес элемента 0 (первого элемента)?

У массива размер элемента 4 байта. Смещение элемента i равно i x размер_элемента. Каково смещение (в байтах) элемента 5?

У массива базовый адрес 2000 и размер элемента 4 байта. Каков адрес элемента 7?

Достижение любого элемента массива занимает одно умножение, одно сложение и одно чтение — одну и ту же фиксированную работу независимо от индекса. Достижение элемента 9000 большого массива по сравнению с достижением элемента 3 занимает: введи 1, если столько же работы, 0, если намного больше работы.

Проверь себя

Викторина

Почему программа может достичь arr[i] за константное время — с одинаковой скоростью для любого индекса?

Итог

Базовый адрес массива — это байтовый адрес его первой ячейки, фиксированная опора, на которую ссылается имя массива. Индекс элемента — это его позиция, отсчитанная от 0; его смещение — это сколько байтов за базовым адресом начинается его ячейка, равное индекс × размер_элемента. Поэтому адрес элемента i — это base_address + (i × element_size) — одно умножение, одно сложение. Элемент 0 — первый элемент, потому что его смещение 0 × element_size = 0, что помещает его точно на базовый адрес; ни у какого другого индекса нет нулевого смещения. Поскольку формула использует одну и ту же фиксированную работу для любого индекса и никогда не трогает длину массива или другие элементы, достижение любого элемента занимает константное время. Эта арифметика адресов за константное время верна только потому, что массив непрерывен и сделан из ячеек одинакового размера.

Продолжить восхождение ↑Объекты как ключ-значение