Массив здорового человека
Теперь в 3D!

В прошлой статье разбирались достоинства и недостатки различных форм представления массивов в памяти. В этот раз рассмотрим трёхмерный случай (и вообще \(N\)-мерный) и обратим внимание на то, как производится пересчёт логических координат в фактические.

Сперва вернёмся к двумерному случаю. Обращение к \(j\)-у элементу, раположенному в \(i\)-й строке, выглядит следующим образом: array_of_a_healthy_man[i * w + j] (\(w\) — количество элементов в строке). На рисунке представлено логическое и фактическое представление двумерного массива. Таким образом, слагаемое \(i \times w\) означает «пропустить \(i\) строк, содержащих по \(w\) элементов».

Двумерный массив вытягивается в «змейку». Для удобства восприятия строки раскрашены в разные оттенки.

Добавим ещё одно измерение.

Сверху — логическое представление, внизу — фактическое (массив представляет собой единый фрагмент в памяти).

Подобно тому, как в двумерном случае было необходимо «пропускать» строки при поиске нужной, теперь необходимо сперва ещё и «пропустить» несколько двумерных массивов в поисках нужного. Таким образом, обращение к элементу будет выглядеть так: array_of_a_healthy_man[i * h * w + j * w + k] (где \(w\) — количество элементов в строке, \(h\) — количество строк). Добавленное слагаемое \(i \times h \times w\) значит следующее: «пропустить» \(i\) двумерных массивов по \(h \times w\) элементов каждый.

Общий случай

Теперь рассмотрим общий случай. Пусть количество измерений равно \(N\) (\(N \geq 1\), \(N\) — целое), а измерения \(D = d_{1}, d_{2}, ..., d_{N}\) (\(d_{k} \geq 1\)), индексы элементов в соответствующих измерениях — \(I = i_{1}, i_{2}, ..., i_{N}\) (\(0 \leq i_{l} \leq d_{l} - 1\)). Тогда функция \(M(D, I)\) показывает, какой индекс в «линейном» массиве будет иметь элемент с индексом \(I\) в массиве размерностью \(D\).

\(M(d_{1}, d_{2}, ..., d_{N}, i_{1}, i_{2}, ..., i_{N})\) \(= \left\{ \begin{array}{c} i_{1}, N = 1 \\ i_{N} \times {\displaystyle \prod_{j=1}^{N-1} d_{j}} + M(d_{1}, d_{2}, ..., d_{N-1}, i_{1}, i_{2}, ..., i_{N-1}), N \geq 2 \\ \end{array} \right.\)

Для примера рассчитаем индекс для элемента четырёхмерного массива. Прямой ход рекурсии.

\(M(d_{1}, d_{2}, d_{3}, d_{4}, i_{1}, i_{2}, i_{3}, i_{4})\) \(= i_{4} \times {\displaystyle \prod_{j=1}^{3} d_{j}} + M(d_{1}, d_{2}, d_{3}, i_{1}, i_{2}, i_{3})\) \(= i_{4} \times d_{1} \times d_{2} \times d_{3} + M(d_{1}, d_{2}, d_{3}, i_{1}, i_{2}, i_{3})\)

\(M(d_{1}, d_{2}, d_{3}, i_{1}, i_{2}, i_{3})\) \(= i_{3} \times {\displaystyle \prod_{j=1}^{2} d_{j}} + M(d_{1}, d_{2}, i_{1}, i_{2})\) \(= i_{3} \times d_{1} \times d_{2} + M(d_{1}, d_{2}, i_{1}, i_{2})\)

\(M(d_{1}, d_{2}, i_{1}, i_{2})\) \(= i_{2} \times {\displaystyle \prod_{j=1}^{1} d_{j}} + M(d_{1}, i_{1})\) \(= i_{2} \times d_{1} + M(d_{1}, i_{1})\)

\(M(d_{1}, i_{1})= i_{1}\)

Обратный ход рекурсии.

\(M(d_{1}, d_{2}, i_{1}, i_{2})\) \(= i_{2} \times d_{1} + M(d_{1}, i_{1})\) \(= i_{2} \times d_{1} + i_{1}\)

\(M(d_{1}, d_{2}, d_{3}, i_{1}, i_{2}, i_{3})\) \(= i_{3} \times d_{1} \times d_{2} + i_{2} \times d_{1} + i_{1}\)

\(M(d_{1}, d_{2}, d_{3}, d_{4}, i_{1}, i_{2}, i_{3}, i_{4})\) \(= i_{4} \times d_{1} \times d_{2} \times d_{3} + i_{3} \times d_{1} \times d_{2} + i_{2} \times d_{1} + i_{1}\)

Результат получен. В ходе вычислений появлялись частные случаи, например, формула при \(N=3\). Поставим в соответствие \(d_{1}\), \(d_{2}\), \(d_{3}\) измерения \(x\), \(y\), \(z\), а \(i_{3}\), \(i_{2}\), \(i_{1}\) — координаты \(i\), \(j\), \(k\).

\(M(d_{1}, d_{2}, d_{3}, i_{1}, i_{2}, i_{3})\) \(= M(x, y, z, k, j, i)\) \(= i_{3} \times d_{1} \times d_{2} + i_{2} \times d_{1} + i_{1}\) \(= i \times x \times y + j \times x + k\)

Получилось то же, что было проиллюстрировано выше.

Целесообразность использования массивов больших размерностей оставим за рамками этой статьи. По крайней мере, это неплохое упражнение на индукцию.

20 апреля 2015
Массив здорового человека
© MMXIMMXX
Светлая тема / тёмная тема