Проектирование трансляторов
Выражение (ui-li+1) задает число различных значений, кото-
рые может принимать i-индекс.
Значение произведения (u2-l2+1)*(u3-l3+1) представляет со-
бой число различных пар значений, которые могут принимать второй
и третий индексы, а также расстояние между элементами массива,
отличающимися только на одну единицу в первом индексе.
Расстояние между элементами, отличающимися на 1 в i-индексе,
известно как i-й шаг. Так, в приведенном выше примере первый шаг
s1 состовляет (u2-l2+1)*(u3-l3+1). Второй шаг s2 равен (u3-l3+1).
Третий шаг s3 составляет 1.
Ясно, что вычисление адресов элементов массива в процессе
прогона может занимать много времени. Поэтому рекомендуется при
программировании по возможности избегать выборки из массивов,
особенно из многомерных. Тем не менее, шаги могут вычисляться
только один раз и храниться в статической части массива наряду с
границами. Такая статическая информация часто называется описате-
лем массива. В этой же части массива наряду с нижней и верхней
границами и шагом для каждой размерности может храниться указа-
тель на элементы массива. Нижняя и верхняя границы требуются для
проверки правильности нахождения индексов в пределах границ, а
шаги и нижние границы - при обращении к конкретным элементам мас-
сива.
2.2 Обращение к элементам массива с помощью векторов Айлифа
Айлиф разработал свой способ обращения к элементам массивов.
Этот способ требует для хранения массива больше памяти, но зато
обращение к элементу выполняется быстрее. Вместе с каждым масси-
вом хранится набор указателей. Так, например, массив, определен-
ный как
B[4:6,-2:1,0:1]
хранился бы в виде структуры, представленной ниже на рис.
20.6.
┌──────┐ ─ ─ ─ ─ i
С │ ──┼───────────────────────────> │ │ (0)
└──────┘ D ─ ─ ─ ─
│ │ (1)
─ ─ ─ ─
│ │ (2)
─ ─ ─ ─
│ │ (3)
┌───────┐
┌─────────────────────────────┼── │ 4
│ ├───────┤
│ ┌────────┼── │ 5
│ │ ├───────┤
│ │ │ │ 6
│ │ └────┼──┘
│ │ │
│ │ │ j
│ │ │
│ │ │
│ │ └──────┐
E │ F │ G │
┌─────┐ │ ┌─────┐ │ ┌─────┐ │
┌─────────┼─ │ │ ┌─────────┼─ │ │ ┌─────────┼─ │ │-2
│ ├─────┤ │ │ ├─────┤ │ │ ├─────┤ │
│ ┌─────┼─ │ │ │ ┌─────┼─ │ │ │ ┌─────┼─ │ │-1
│ │ ├─────┤ │ │ │ ├─────┤ │ │ │ ├─────┤ │
│ │ ┌─┼─ │<─┘ │ │ ┌─┼─ │<─┘ │ │ ┌─┼─ │<─┘ 0
│ │ │ ├─────┤ │ │ │ ├─────┤ │ │ │ ├─────┤
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ 1
│ │ │ └───┼─┘ │ │ │ └───┼─┘ │ │ │ └───┼─┘
│ │ │ │ │ │ │ │ │ │ │ │
H┌─┬─┬─┬─┬─┬─┬───┬────┬─┬─┬─┬─┬─┬─┬───┬────┬─┬─┬─┬─┬─┬─┬────┬───┐
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
k└─┴─┴─┴─┴─┴─┴───┴────┴─┴─┴─┴─┴─┴─┴───┴────┴─┴─┴─┴─┴─┴─┴────┴───┘
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Рис. 20.6 Схема обращения к элементам массива с помощью век-
торов Айлифа
Пусть запись вида (B+5) означает содержимое по адресу B+5.
Тогда к элементу B[i,j,k] можно обратиться следующим образом:
(((C)+i)+j)+k
При этом выбирается содержимое ячейки C и к нему прибавляет-
ся значение индекса i, затем по полученному в результате этого
адресу выбирается содержимое, которое дает указатель на следую-
щий более низкий уровень, и т.д.
Важно отметить, что при данном способе обращения к элементу
массива не требуется выполнения операций умножения. Вместе с тем
в рассмотренном примере, кроме вектора для хранения массива, тре-
буется еще один вектор длины 3 и три вектора длины 4, и таким об-
разом, вместо 24 элементов требуется 39. Этот метод оказывается
наиболее экономичным, когда диапазоны изменения индексов увеличи-
ваются от первого к последнему. Наименее всего этот метод эффек-
тивен, когда первый индекс имеет наибольший диапазон изменения.
В приведенном примере не производилось проверки корректнос-
ти индекса. Это может быть достигнуто путем хранения вместе с
каждым элементом вектора Айлифа граничной пары для соответствую-
щего индекса. Правда, в случае прямоугольного массива это могло
бы оказаться неэкономичным. У каждого из элементов векторов E,F и
G в рассматриваемом примере были бы одинаковые граничные пары.
Однако следует обратить внимание на то, что с каждым из этих эле-
ментов могли бы быть связаны и различные граничные пары, что да-
ло бы возможность, используя векторы Айлифа, обращаться к масси-
вам со значительно более сложной структурой.
Так, например, на рис. 20.7 показан набор векторов Айлифа,
позволяющих обращаться к трехмерному массиву, элементы которого
хранятся в следующем порядке:
B[4,-1,-1] B[5,1,2] B[6,0,0]
B[4,-1, 0] B[5,2,2] B[6,0,1]
B[4,-1, 1] B[5,2,3] B[6,0,2]
B[4,-1, 2] B[5,3,2] B[6,0,3]
B[4, 0, 0] B[5,3,3] B[6,0,4]
B[4, 0, 1] B[5,3,4] B[6,0,5]
B[4, 0, 2] B[5,3,5]
B[4, 0, 3]
B[4, 0, 4]
B[4, 0, 5]
B[4, 0, 6]
┌─────┬─┬─┐
│ │4│6│