другой - на максимальный размер, до которого она выросла при ра-
боте с текущим блоком. Именно значение этого второго указателя
при выходе из блока и дает объем статического рабочего стека,
включаемого в соответствующую рамку.
2. ПРЕДСТАВЛЕНИЕ МАССИВОВ
2.1 Прямоугольные массивы
Простейшие массивы (одномерные) естественно представляются
векторами, т.к. они хорошо согласуются в том смысле, что для по-
лучения относительного адреса элемента массива в векторе надо вы-
честь нижнюю границу по измерению из индекса элемента.
Из многомерных массивов рассмотрим сначала прямоугольные. Их
также возможно представлять векторами. Для реализации выборки или
засылки в массив надо получить относительный адрес нужного эле-
мента в векторе по значениям индексов этого элемента.
Предполагая линейное расположение всех точек n-мерного прос-
транства (n - размерность), соответствующего массиву, мы можем
считать первые измерения старшими и тогда рядом располагаются
элементы, соседние по последнему измерению - так называемый
ПРЯМОЙ порядок, либо наоборот - ОБРАТНЫЙ порядок. Например, в
языке Алгамс поддерживается прямой порядок, в Фортране - обрат-
ный, а в АЛГОЛе-60 представление многомерных массивов никак не
фиксируется.
Когда в программе выбирается конкретный элемент массива, его
адрес внутри динамической части должен вычисляться в процессе
прогона. Рассмотрим массив:
[1:10,-5:5] int Table
Будем считать, что элементы записаны в лексикографическом
порядке индексов, т.е. элементы хранятся в следующем порядке:
Table[1,-5], Table[1,-4] ......... Table[1,5],
Table[2,-5], Table[2,-4] ......... Table[2,5],
.
.
.
Table[10,-5], ...................... Table[10,5]
Адрес конкретного элемента вычисляется как смещение по отно-
шению к базовому адресу (адресу первого элемента) массива:
ADDR(Table[I,J])=ADDR(Table[l1,l2])+(u2-l2+1)*(I-l1)+(J-l2)
Здесь l1 и u1 - нижняя и верхняя границы первой размерности
и т.д. и считается, что каждый элемент массива занимает единицу
объема памяти.
Для трехмерного массива соответствующая формула имеет вид:
ADDR(Table[I,J,K])=ADDR(Table[l1,l2,l3])+
(u2-l2+1)*(u3-l3+1)(I-l1)+
(u3-l3+1)*(J-l2)+K-l3
Выражение (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│
└──┼──┴─┴─┘ ─ ─ ─ ─ ─
└────────────────────────────> │ │
─ ─ ─ ─ ─
│ │
─ ─ ─ ─ ─
│ │
─ ─ ─ ─ ─
│ │
┌────┬──┬──┐
┌──────────────────────────────┼── │-1│ 0│
│ ├────┼──┼──┤
│ ┌────────┼── │ 1│ 3│
│ │ ├────┼──┼──┤
│ │ │ │ 0│ 0│
│ │ └─┼──┴──┴──┘
│ │ │
│ │ │
│ ─ ─ ─ ─ ─ ─ │ ┌─────┘
│ │ │<──┘ │
│ ┌─────┬──┬──┐ │
│ ┌───┼─ │ 2│ 2│ │
┌─────┬──┬──┐ │ │ ├─────┼──┼──┤ ┌─────┬───┬──┐