ячейках в порядке возрастания. Так, описание ARRAY А [1:M, 1:N]
порождает
┌────────────────────────┐ ┌─────────────────────┐
│ Указатель на строку 1 ├─────────┤ A[1, 1] ... A[1, N] │
├────────────────────────┤ └─────────────────────┘
│ Указатель на строку 2 ├───────┐ ┌─────────────────────┐
├────────────────────────┤ └─┤ A[2, 1] ... A[2, N] │
│ ... │ └─────────────────────┘
├────────────────────────┤ ┌─────────────────────┐
│ Указатель на строку M ├─────────┤ A[M, 1] ... A[M, N] │
└────────────────────────┘ └─────────────────────┘
Вектор указателей строк хранится в той области данных, с которой
ассоциируется массив, в то время как собственно массив хранится
в отдельной области данных. Адрес элемента массива А[i, j] есть
CONTENTS(i-1) + (j-1).
Первое преимущество этого метода состоит в том, что при
вычислении адреса не нужно выполнять операцию умножения. Другим
является то, что не все строки могут находиться в оперативной
памяти одновременно. Указатель строки может содержать некоторое
значение, которое вызовет аппаратное или программное прерывание
в случае, если строка в памяти отсутствует. Когда возникает
прерывание, строка вводится в оперативную память из на место
другой строки.
Если все строки находятся в оперативной памяти, то массив
требует больше места, поскольку необходимо место и для вектора
указателей.
Когда известно, что матрицы разреженные ( большинство
элементов - нули ), используются другие методы. Может быть
применена схема хеш-адресации, которая базируется на значениях i
и j элемента массива А[i, j] и ссылается по хеш-адресу на
относительно короткую таблицу элементов массива. В таблице
хранятся только ненулевые элементы матрицы.
Многомерные массивы
Мы рассмотрим размещение в памяти и обращение к
многомерным массивам, описанным, следующим образом:
ARRAY A[L1:U1, L2:U2, ..., Ln:Un]
Метод заключается в обобщении первого метода, предложенного для
двумерного случая; он также применим и для одномерного массива.
Подмассив A[i,*, ..., *] содержит последовательность
A[L1,*, ..., *], A[L1+1,*, ..., *], и т.д. до A[U1,*, ..., *].
Внутри подмассива A[i,*, ..., *] находятся подмассивы
A[i,L2,*, ..., *], A[i,L2+1,*, ..., *], ... и A[i,U2,*, ..., *].
Это повторяется для каждого измерения. Так, если мы продвигаемся
в порядке возрастания по элементам массива, быстрее изменяются
последние индексы:
┌───────────────────────────────────────┐ ┌─────────┐ ┌───────┐
│ подмассив A[L1] │ │ A[L1+1] │ │ A[U1] │
│ ┌────────┐ ┌──────────┐ ┌────────┐│ │ │ │ │
│ │A[L1,L2]│ │A[L1,L2+1]│ ... │A[L1,U2]││ │ │ ... │ │
│ └────────┘ └──────────┘ └────────┘│ │ │ │ │
└───────────────────────────────────────┘ └─────────┘ └───────┘
Вопрос заключается в том, как обратиться к элементу
A[i,j,k, ..., l,m]. Обозначим
d1 = U1-L1+1, d2 = U2-L2+1, ..., dn = Un-Ln+1.
То есть d1 есть число различных значений индексов в i-том
измерении. Следуя логике двумерного случая, мы находим начало
подмассива A[i,*, ..., *]
BASELOC + (i-L1)*d2*d3*...*dn
Где BASELOC - адрес первого элемента A[L1,L2,...,Ln], а
d2*d3*...*dn - размер каждого подмассива A[i,*,...,*]. Начало
подмассива A[i,j,*,...,*] находится затем добавлением
(j-L2)*d3*...*dn к полученному значению.
Действуя дальше таким же образом, мы окончательно получим:
BASELOC + (i-L1)*d2*d3*...*dn + (j-L2)*d3*...*dn
+ (k-L3)*d4*...*dn + ... + (i - Ln-1)*dn + m - Ln
Выполняя умножения, получаем CONST_PART + VAR_PART, где
CONST_PART = BASELOC - ((...(L1*d2+L2)*d3+L3)*d4+...+Ln-1)*dn+Ln)
VAR_PART = (...((i*d2)+j)*d3+...+1)*dn + m
Значение CONST_PART необходимо вычислить только 1 раз и
запомнить, т.к. оно зависит лишь от нижних и верхних границ
индексов и местоположения массива в памяти. VAR_PART зависит от
значений индексов i,j,...,m и от размеров измерений d2,d3,...,
dn. Вычисление VAR_PART можно представить в более наглядном виде:
VAR_PART = первый индекс (i)
VAR_PART = VAR_PART*d2 + второйиндекс (j)
VAR_PART = VAR_PART*d3 + третийиндекс (k)
.....
VAR_PART = VAR_PART*dn + n-йиндекс (m)
Информационные векторы
В некоторых языках верхняя и нижняя границы массивов известны
во время трансляции, поэтому компилятор может выделить память для
массивов и сформировать команды, ссылающиеся на элементы массива,
┌────┬────┬────┐
│ L1 │ U1 │ d1 │
├────┼────┼────┤
│ L2 │ U2 │ d2 │
│ . │ . │ . │ Описание массива
│ . │ . │ . │ A[L1:U1,...,Ln:Un]
│ . │ . │ . │
│ Ln │ Un │ dn │
├────┼────┴────┤
│ n │CONSTPART│
├────┴─────────┤
│ BASELOC │
└──────────────┘
Рис. . Информационный вектор для массива
используя верхние и нижние границы и постоянные значения d1,d2,..
.,dn. В других языках это невозможно т.к. границы могут
вычисляться во время счета. Поэтому нужен описатель для массива,
содержащий необходимую информацию. Этот описатель для массива
называется допвектор ( dope vector ) или информационный вектор.
Информационный вектор имеет фиксированный размер, который
известен при компиляции, следовательно, память для него может
быть отведена во время компиляции в области данных, с которой
ассоциируется массив. Память для самого массива не может быть
отведена до тех пор, пока во время счета не выполнится вход в
блок, и котором описан массив. При входе в блок вычисляются
границы массива и производится обращение к программе
распределения памяти для массивов. Здесь же вносится в
информационный вектор необходимая информация.
Какая информация заносится в информационный вектор? Для
предложенной выше n-мерной схемы нам как минимум нужны d2,...dn
и CONST_PART. Если перед обращением к массиву нужно проверять
правильность задания индексов, то следует также занести в
информационный вектор значения верхних и нижних границ.
5. Память для структур
Существует несколько альтернатив для определения новых
типов данных как структур, составленных из типов данных,
определенных ранее. Величины такого типа мы называем
структурными величинами. Существуют различные подходы к
реализации этих конструкций. Отличия обычно касаются следующих
вопросов:
Как выделять память для структурных величин?
Как строить структурные величины?
Как ссылаться на компоненту структурной величины?
Как освобождать память?
Записи по Хоору
Определение нового типа данных имеет вид
RECORD <идентификатор> ( <компонента>,
<компонента>, . . . , <компонента> )
где каждая компонента имеет вид
<простой тип> <идентификатор>
Причем <простой тип> является одним из основных типов языка -
REAL, INTEGER, POINTER и т.д. Здесь во время компиляции известны
все характеристики всех компонент, включая тип данных, на которые
могут ссылаться указатели. Во время счета не нужны описатели ни
для самой структуры, ни для ее компонент, причем может быть
сгенерирована эффективная программа.
Любая структурная величина с n компонентами может храниться в
памяти в виде:
┌──────────────┬──────────────┬─────────┬──────────────┐
│ Компонента 1 │ Компонента 2 │ ... │ Компонента n │
└──────────────┴──────────────┴─────────┴──────────────┘
Поскольку при компиляции известны все характеристики, то
известен также объем памяти, необходимый для каждой компоненты,
и, следовательно, компилятор знает смещение каждой компоненты
относительно начала структурной величины. Для упрощения сбора
мусора лучше всего присвоить номер каждому типу данных ( включая
типы, определенные программистом) и иметь описатель для каждого
указателя. Описатель будет содержать номер, описывающий тип
величины, на которую в данный момент ссылается указатель.
Память для указателей и их описателей может быть выделена
компилятором в области данных, с которой они связаны; это не
трудно, так как они имеют фиксированную длину. Для хранения
текущих значений структурных величин может быть использована
отдельная статическая область данных и специальная программа для