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

Эта работа не обязательна для выполнения.

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

Введение

Основная идея многомерных массивов в том, что для их индексирования используется несколько индексов. На индексы ставится еще одно ограничение: они должны быть последовательны, от какого-то минимума до максимума (для каждого измерения по отдельности). Обычно индексы идут от 0 до длины этого измерения.

Сложность заключается в расположении элементов в памяти. Основных подхода 2: векторы Iliffe и использование линейной памяти. У линейной памяти, в свою очередь, есть выбор очереди представления измерений (номера индекса) в памяти. Также существует метод оптимизации Dope Vector, который позволяет ускорить вычисление линейного индекса.

На картинке ниже например, индекс элемента 71 будет 3 (array), 1 (row), 2 (column). Заметьте, что на картинке индексирование идет с 1.

Iliffe

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

То есть будет по одному независимому линейному массиву для каждого из рядов. Преимущество в том, что можно сделать, чтобы ряды имели разную длину. Всего их будет 9 штук.

10 | 11 | 12

20 | 21 | 22

... больше рядов здесь

70 | 71 | 72

80 | 81 | 82

90 | 91 | 92

Начало каждого из рядов будет иметь свой адрес в памяти. Этот адрес идет в массив следующего уровня — массив рядов, идексируемый номером ряда. Этих будет всего 3.

Адрес ряда (10|11|12) | Адрес ряда (20|21|22) | Адрес ряда (30|31|32) --> x

Адрес ряда (40|41|42) | Адрес ряда (50|51|52) | Адрес ряда (60|61|62) --> y

Адрес ряда (70|71|72) | Адрес ряда (80|81|82) | Адрес ряда (90|91|92) --> z

И финальный массив будет хранить адреса этих массивов с адресами массивов рядов: x|y|z.

Задание

Реализуйте код для таких массивов. Начните с 2 измерений. Потом сделайте обощенную версию (для любого количества измерений).

Интерфейс будет, например, вот такой:

• Iliffe createIliffe(std::span<size_t> sizes);. sizes имеет размерность каждого из измерений (количество array, количество row, количество column)
• T* getElement(Iliffe* array, std::span<size_t> indices) возвращает нужный элемент, по индексам, заданными параметром. Проверяйте, чтобы количество индексов совпадало с количеством измерений, заданным при создании.

Можете заморочится с template, чтобы делать проверку измерений при компиляции, а не при запуске:

• Iliffe<N> createIliffe(std::array<size_t, N> sizes). N задан через template <size_t N>.
• T* getElement(Iliffe<N>* array, std::array<size_t, N> indices).

Линейная память

Идея в том, что элементы будут хранится не в независимых массивах, а в одном. Для двухмерных массивов, например:

    0   1   2
0 | 0 | 1 | 2 |
1 | 3 | 4 | 5 |
2 | 6 | 7 | 8 |

Элементы из ячеек можно расположить в памяти вот так (по рядам, row-major order):

0 1 2 3 4 5 6 7 8

Или вот так (по колонкам, column-major order):

0 3 6 1 4 7 2 5 8

Для многомерных массивов это обобщается следующим образом:

• row-major значит элементы идут в памяти справа налево по измерениям (arr[a][b][c] --> c, b, a).
• column-major значит слева направо (arr[a][b][c] --> a, b, c).

Заметьте, что порядок индексирования не меняется, меняется только расположение элементов в памяти.

Этот порядок указывает, как будут изменятся индексы, если пройдем по элементам как они расположены в памяти. Ниже демонстрируется, как в зависимости от row/column-major расположения элементов изменяюся их индексы.

(0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2)
  0     1     2     3     4     5     6     7     8

(0,0) (1,0) (2,0) (0,1) (1,1) (2,1) (0,2) (1,2) (2,2)
  0     3     6     1     4     7     2     5     8

Аналогично происходит и во многомерных массивах (все индексы справа налево или слева направо).

Поиск индекса

Давайте рассмотрим как найти нужный линейный индекс по индексам для каждого из измерений, на примере трехмерного массива с картинки выше, в row-major расположении.

Идея в том, что мы можем представить, будто все элементы в группах по 3, но они же находятся линейно в памяти. То есть, линейно в памяти они идут слева направо, сверху вниз; если arr[a][b][c] это синтаксис индексирования, a это номер ряда (на примере ниже), b это номер группы по 3 в этом ряду, c это индекс внутри группы.

(10|11|12) | (20|21|22) | (30|31|32)
(40|41|42) | (50|51|52) | (60|61|62)
(70|71|72) | (80|81|82) | (90|91|92)

Добавление каждого индекса a перепрыгивает через 9 элементов (весь ряд). Аналогично, добавление 1 к b заставляет линейный индекс перепрыгнуть через 1 группу (3 линейних индекса). Добавление 1 к c меняет индекс на 1.

Можем взглянуть слегка по-другому: каждый индекс a соответствует 3 индексам b. Каждый индекс b соответствует 3 индексам c.

Один из подходов будет найти сначала индекс группы по 3 — это будет индекс ряда a, раз по 3 группы в каждом ряду, + b. Потом найти линейный индекс — это будет количество пропущенных элементов в группах по 3, раз 3, + c.

$$i = 3(3a + b) + c$$

Другой подход — посчитать сколько элементов пропускается с каждым пропущенным рядом: 3 группы по 3 элемента, то есть всего 9. Это же можно вывести раскрыв скобки:

$$i = 9a + 3b + c$$

Эти 9, 3 или 1 для c указывают сколько ячеек “стоит” каждый из индексов, поэтому называются cost. Обозначается как $D_j$, где $j$ это номер измерения (справа налево, потому что row-major).

Если обозначить как $n_j$ длину измерения $j$ (длину интервала индексов), выражение для $D_j$ можно рекурсивно обобщить:

$$\begin{align} & D_j = D_{j - 1} * n_{j - 1} \\ & D_0 = 1 \end{align}$$

Задание

Реализуйте это в коде:

• Linear createLinear(std::span<size_t> sizes, Order order);. Общее количество элементов будет равно произведению всех sizes. order будет либо RowMajor, либо ColumnMajor (через enum class).
• T* getElement(Linear* array, std::span<size_t> indices).
• std::span<T> elements(Linear* array) — дает доступ к линейному массиву с элементами.

Аналогично можете сделать для N и template.

Dope Vector

Dope Vector применяется в случаях, где начальный и конечный индекс не равны 0 и длине - 1. То есть он применим по факту только для массивов с нестандартными интервалами индексов.

Для нестандартных интервалов индексов индексирование на памяти в простом подходе производится отниманием нижней границы интервала (чтобы превратить первый доступный индекс в 0 — первый доступный линейный индекс). Длина интервала очевидно будет верхний - нижний предел + 1 (потому что верхний предел включен в интервал).

Формулой поиск можно выразить вот так ($l_j$ нижний предел для измерения $j$, $h_j$ — верхний, $N$ — число измерений, $k_j$ — $j$ измерение запрашиваемого индекса, $n_j$ длина интервала индексов измерения $j$):

$$\begin{align} & n_j = h_j - l_j + 1 \\ & D_0 = 1 \\ & D_j = n_{j - 1} * D_{j - 1} \\ & i = \sum_{j=0}^{N - 1} (k_j - l_j) D_j = \sum_{j=0}^{N - 1} k_j D_j - c \\ & c = \sum_{j=0}^{N - 1} l_j D_j \end{align}$$

Таким образом, индекс можно вывести не отнимая нижних границ, вычислив заранее все $D_j$ и $c$, что ускоряет вычисление линейного индекса.

Dope Vector означает все значения $D_j$ и значение $c$.

Задание

Сделайте возможность хранить элементы по индексам не с нуля. После чего, добавьте использование Dope Vector-a в реализацию. Вычисляйте Dope Vector один раз при создании.

using SignedSize = std::make_signed_t<size_t>;

struct Range
{
    SignedSize from;
    SignedSize toInclusive;
};

• LinearRanged createLinearRanged(std::span<Range> ranges, Order order) — принимает интервалы индексов, считает длины и Dope Vector само, хранит полученную информацию в поле структуры.
• T* getElement(LinearRanged* array, std::span<SignedSize> indices).