В прошлой статье разбирались достоинства и недостатки различных форм представления массивов в памяти. В этот раз рассмотрим трёхмерный случай (и вообще \(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\)

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

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