Boosty
Светлая тема /
тёмная тема
Массив здорового человека
Теперь в 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\]
Получилось то же, что было проиллюстрировано выше.
Целесообразность использования массивов больших размерностей оставим за рамками этой статьи. По крайней мере, это неплохое упражнение на индукцию.