Многомерные массивы

Введение и общая идея

Многомерный массив - структура данных, в которой элементы организованы в несколько измерений и индексируются набором индексов, по одному на каждое измерение.

Понятие многомерного массива обобщает идею одномерного массива: вместо одного индекса используется набор индексов длины $k$. Такой массив часто называют $k$-мерным. Наиболее распространённые частные случаи — это $2$-мерные (матрицы) и трёхмерные массивы, используемые, например, для представления объёмных данных или изображений в нескольких слоях.

Многомерные массивы используются для представления табличных данных, матриц в алгебре, таблиц значений функций нескольких переменных, а также для хранения объектов, имеющих натуральную структуру измерений (строки/столбцы/слои).

Физическое представление в памяти

В памяти многомерный массив обычно хранится непрерывно как последовательность элементов. Два основных способа расположения элементов — построчно (row-major) и по столбцам (column-major). Адрес элемента вычисляется по формуле смещения относительно базового адреса массива; для $2$-мерного массива в построчном порядке смещение часто записывают как $\mathrm{offset}=\mathrm{base}+\bigl((i\cdot n_{\text{cols}}+j)\cdot s\bigr)$.

Row-major - стратегия упаковки элементов многомерного массива в линейную память, при которой элементы одной строки идут подряд в памяти.

Для произвольного $k$-мерного массива общая формула смещения в терминах размеров измерений и индексов может быть записана компактно как $\mathrm{offset}=\mathrm{base}+\left(\sum_{t=1}^{k} i_t\prod_{u=t+1}^{k} n_u\right)\cdot s$. Эта формула показывает, что для вычисления смещения каждого индекса умножают на произведение размеров последующих измерений и суммируют результаты, затем умножают на размер одного элемента.

Column-major - альтернатива row-major, при которой элементы одного столбца располагаются подряд; формула смещения для $2$-мерного массива в column-major даётся как $\mathrm{offset}=\mathrm{base}+\bigl((j\cdot n_{\text{rows}}+i)\cdot s\bigr)$.

Индексация и проверки границ

Индексы в многомерном массиве обычно принимают целые значения в пределах размеров соответствующих измерений. Для $2$-мерного массива с $n\cdot m$ элементами в простом представлении индексы удовлетворяют условиям $0\le i<n$ и $0\le j<m$, где $0\le i<n$ описывает допустимые значения для индекса строк, а $0\le j<m$ — для индекса столбцов.

Проверка границ (bounds checking) — важная операция безопасности: она предотвращает доступ за пределы выделенной памяти. Без проверки неправильно вычисленное смещение может привести к ошибкам или уязвимостям. Для оценки количества итераций, требуемых для полного перебора всех элементов в $2$-мерном массиве, используют выражение $n\cdot m$.

Операции: срезы, трансформация и пересчёт индексов

Срез (slice) - подмассив, получаемый фиксированием некоторых индексов или диапазонов индексов; срез имеет меньше измерений или уменьшенные размеры измерений по сравнению с исходным массивом.

При получении среза чаще всего меняется только логическая форма (shape) массива: например, при выборе строки из матрицы формы $m\times n$ получится одномерный массив длины, равной числу столбцов. При этом физически элементы могут оставаться на тех же позициях в памяти, и срез определяется лишь базовым смещением и набором новых шагов (strides).

Шаги (strides) — это набор величин, показывающих, на сколько байт или элементов нужно сдвинуться в памяти при увеличении соответствующего индекса на единицу. Для простого представления в row-major шаг для первого индекса равен произведению размеров всех последующих измерений, для следующего — произведению оставшихся и т.д. Это выражается в формуле общего вида через произведения и суммы, например, в формуле смещения $\mathrm{offset}=\mathrm{base}+\left(\sum_{t=1}^{k} i_t\prod_{u=t+1}^{k} n_u\right)\cdot s$.

Асимптотика и алгоритмы обхода

Многие алгоритмы, работающие с многомерными массивами, используют вложенные циклы по каждому измерению. Общее число итераций при полном переборе всех элементов $k$-мерного массива равно произведению размеров по всем измерениям, записываемому как $\displaystyle\prod_{t=1}^{k} n_t$.

Выбор порядка обхода (например, сначала по строкам, затем по столбцам) влияет на производительность из-за кеширования: последовательный доступ по размещению в памяти более эффективен. Для матрицы в row-major эффективнее внешним циклом сделать перебор строк, внутренним — столбцов, поскольку тогда адреса смещаются последовательно на единицу элемента.

Многомерные массивы в языках программирования

В разных языках программирования реализация многомерных массивов может отличаться: где-то это синтаксический сахар над одномерным массивом с вычислением смещений, где-то — массив массивов с несмежным расположением строк в памяти. В языках низкого уровня объявление фиксированных размеров часто выглядит как пример встраивания размеров прямо в объявление, например: $3$ и $4$.

Важно различать логическую форму массива (shape) и физические шаги в памяти (strides). Некоторые библиотеки (например, научные библиотеки) позволяют иметь общий буфер памяти и различные представления этого буфера в виде массивов разной формы без копирования данных — это достигается манипуляцией базовым смещением и шагами.

Практические примеры вычислений

Рассмотрим ещё один конкретный пример индексации в row-major. Линейный индекс элемента с индексами i и j вычисляется как $i\cdot\text{cols}+j$. Это выражение затем умножается на размер элемента и прибавляется к базовому адресу, что даёт полный адрес в памяти и описывается ранее приведённой формулой смещения $\mathrm{offset}=\mathrm{base}+\bigl((i\cdot n_{\text{cols}}+j)\cdot s\bigr)$.

Линейный индекс - позиция элемента в одномерном представлении массива, соответствующая набору многомерных индексов.

Для оценки объёма памяти массива произвольной размерности удобно использовать формулу общего вида: объём в байтах равен произведению размера элемента на произведение размеров всех измерений, что можно записать как $s\cdot \displaystyle\prod_{t=1}^{k} n_t$.

Заключение: понимание логической структуры многомерных массивов, формул смещения и влияния расположения в памяти позволяет эффективно писать код, правильно оценивать потребности по памяти и оптимизировать доступы для повышения производительности алгоритмов.