Базовый CS с нуля
Массивы как непрерывные ячейки
До сих пор каждая переменная, которую ты видел, хранила одно значение: одно число, один булев, одну строку. Но программе почти всегда нужно хранить много значений одного вида — очки каждого игрока, байты файла, пиксели изображения.
Можно было бы объявить сотню отдельных переменных, но это нерабочий путь. Вместо этого языки дают тебе массив: одно имя, которое ссылается на целую последовательность значений, расположенных по порядку. Первое, что нужно понять о массиве, — это не его синтаксис, а его форма в памяти. Массив не разбросан по памяти случайно. Это единая непрерывная череда ячеек, каждая одного размера, размещённых прямо вплотную друг к другу.
После этого урока ты сможешь представить, где именно в памяти лежит каждый элемент массива и почему эта картина — основа всего, что массивы умеют делать.
После этого урока ты сможешь определить массив как непрерывную череду ячеек одинакового размера, объяснить, почему каждая ячейка массива одного размера, определить, какие адреса занимает небольшой массив, и трассировать раскладку массива-литерала в памяти элемент за элементом.
Вспомни два факта из ранних блоков. Из Блока 02: память — это длинный ряд адресуемых ячеек, у каждой свой числовой адрес, а байт (8 битов) — стандартная единица, которую хранит ячейка. Из Блока 05: у каждого значения есть тип, и тип задаёт, сколько байтов нужно значению — число заданного типа всегда занимает одно и то же фиксированное число байтов.
Массив построен прямо на этих двух фактах. Массив — это последовательность значений, все одного типа, хранимая в памяти как череда ячеек, которые:
- Одинаковы по размеру. Поскольку каждый элемент одного типа, каждому элементу нужно одинаковое число байтов. Значит, каждая ячейка массива одного размера. Назовём этот размер размером элемента.
- Непрерывны. Ячейки лежат прямо вплотную, без разрывов между ними. Массив занимает один непрерывный блок адресов. Это свойство называется непрерывной памятью.
Каждое значение, хранимое в массиве, называется элементом. Если у массива 5 элементов и каждый элемент 4 байта, весь массив — один цельный блок из 5 × 4 = 20 байтов.
Эти два свойства связаны. Одинаковый размер — это то, что делает непрерывность полезной: когда одинаковые ячейки упакованы вплотную, положение любой ячейки совершенно регулярно и предсказуемо. Эту регулярность ты используешь в следующем уроке, чтобы найти любой элемент мгновенно. Пока цель — просто увидеть форму: массив — это аккуратная полоса одинаковых ячеек без разрывов.
Программа ниже строит небольшой массив из 5 чисел. Трассировка показывает, как массив обретает форму ячейка за ячейкой.
1
// Массив-литерал: 5 чисел одного типа.
2
let scores: number[] = [90, 80, 70, 60, 50];
3
4
// Все пять значений живут в одном непрерывном блоке памяти.
5
// Элемент 0 находится в начале блока; остальные следуют
6
// прямо за ним, каждый в ячейке одного размера.
7
8
// У scores 5 элементов.
9
// Если каждое число занимает 4 байта, весь массив — 20 байтов.
- L2 scores — массив из 5 элементов, каждый элемент число, поэтому каждая ячейка одного размера
- L5 Элемент 0 (значение 90) лежит первым; элемент 1 (значение 80) лежит прямо за ним, и так далее
- L6 Без разрывов: ячейки вплотную. Это непрерывная память.
- L9 5 элементов x 4 байта каждый = один цельный блок в 20 байтов
Пройди построение scores шаг за шагом. Каждый прямоугольник — одна ячейка массива; адрес
под каждым прямоугольником — байтовый адрес, с которого эта ячейка начинается. Считаем,
что блок массива начинается с адреса 1000 и каждое число занимает 4 байта, поэтому ячейки
начинаются с 1000, 1004, 1008, 1012, 1016.
1
let scores: number[] =
2
[90, 80, 70, 60, 50];
Почему это работает
Почему массиву нужно, чтобы каждый элемент был одного размера? Если бы элементы могли быть разного размера, ячейки не были бы одинаковыми, и не было бы способа узнать, где кончается один элемент и начинается следующий, не осмотрев их все. Заставляя один тип — а значит, один фиксированный размер — язык гарантирует, что ячейки образуют совершенно регулярную сетку. Именно эта регулярность позволяет программе перепрыгнуть прямо к любому элементу. Последовательность смешанного размера возможна, но это уже не простая сетка вплотную; ей нужен дополнительный учёт. Простой массив меняет гибкость на чистую, предсказуемую форму.
Частая ошибка
Распространённое заблуждение — что элементы массива хранятся «где-то в памяти», а имя массива служит списком отдельных мест. Это не модель массива. Элементы занимают один блок последовательных адресов. Имя массива ссылается на этот блок — а именно на то, где он начинается. Элементы не разбросаны; это единая непрерывная череда.
У массива 6 элементов, и каждый элемент занимает 4 байта. Сколько байтов занимает весь блок массива?
Массив из 8 элементов занимает непрерывный блок в 16 байтов всего. Сколько байтов каждый элемент (размер элемента)?
Блок массива начинается с адреса 1000, и каждый элемент 4 байта. С какого адреса начинается элемент 1 (второй элемент)?
В простом массиве каждый элемент должен быть одного типа, чтобы каждая ячейка была одного размера. Если массив хранит числа, может ли одна ячейка хранить число, а другая — строку из 1 символа другого байтового размера? Введи 1 за да, 0 за нет.
Массив из 5 чисел, каждое 4 байта, начинается с адреса 2000. С какого адреса начинается последний элемент (элемент 4)?
Какова форма массива в памяти?
Массив — это последовательность значений одного типа, хранимая в памяти как череда ячеек одинакового размера, размещённых прямо вплотную друг к другу. Поскольку каждый элемент одного типа, каждому элементу нужно одинаковое число байтов — размер элемента — поэтому каждая ячейка одинакова по размеру. Поскольку ячейки лежат без разрывов между ними, массив занимает один непрерывный блок адресов; это непрерывная память. Массив из N элементов, каждый размером S байтов, — это один цельный блок из N × S байтов. Каждое значение в массиве — это элемент, а имя массива ссылается на начало блока. Эта аккуратная сетка одинаковых ячеек без разрывов — основа всего, что массивы умеют делать, начиная с мгновенного поиска элемента, который ты увидишь в следующем уроке.