Массив здорового человека

Теперь в 3D!

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

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

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

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

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

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

Общий случай

Теперь рассмотрим общий случай. Пусть количество измерений равно N (N ≥ 1, N целое), а измерения D = d1, d2, ... dN (dk ≥ 1), индексы элементов в соответствующих измерениях — I = i1, i2, ... iN (0 ≤ ildl − 1). Тогда функция M(D, I) показывает, какой индекс в «линейном» массиве будет иметь элемент с индексом I в массиве размерностью D.

M(d1, d2, ... dN, i1, i2, ... iN) =
i1, N = 1,
N − 1
iN ×
Π
dj + M(d1, d2, ... dN − 1, i1, i2, ... iN − 1), N ≥ 2.
j = 1

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


M(d1, d2, d3, d4, i1, i2, i3, i4) = i4 ×
3
Π
j = 1
dj + M(d1, d2, d3, i1, i2, i3) = i4 × d1 × d2 × d3 + M(d1, d2, d3, i1, i2, i3);
M(d1, d2, d3, i1, i2, i3) = i3 ×
2
Π
j = 1
dj + M(d1, d2, i1, i2) = i3 × d1 × d2 + M(d1, d2, i1, i2);
M(d1, d2, i1, i2) = i2 ×
1
Π
j = 1
dj + M(d1, i1) = i2 × d1 + M(d1, i1);
M(d1, i1) = i1.

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

M(d1, d2, i1, i2) = i2 × d1 + M(d1, i1) = i2 × d1 + i1;

M(d1, d2, d3, i1, i2, i3) = i3 × d1 × d2 + i2 × d1 + i1;

M(d1, d2, d3, d4, i1, i2, i3, i4) = i4 × d1 × d2 × d3 + i3 × d1 × d2 + i2 × d1 + i1.

Результат получен. В ходе вычислений появлялись частные случаи, например, формула при N = 3. Поставим в соответствие d1, d2, d3 измерения x, y, z, а i3, i2, i1 — координаты i, j, k.

M(d1, d2, d3, i1, i2, i3) = M(x, y, z, k, j, i) = i3 × d1 × d2 + i2 × d1 + i1 = i × x × y + j × x + k.

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

* * *

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

20 апреля 2015 · массивы · программирование
Оставить комментарий (отменить)