Реферат: Распределение памяти
собственно на значение величины. Это бывает необходимо в случае
когда во время компиляции невозможно определить для каждого
использования указателя тип величины, на которую он ссылается.
4. Память для массивов
Мы предполагаем, что каждый элемент массива или вектора
занимает в памяти одну ячейку. Случай большего числа ячеек
полностью аналогичен.
Векторы
Элементы векторов ( одномерных массивов ) обычно помещаются
в последовательных ячейках области данных в порядке возрастания
или убывания адресов. Порядок зависит от машины и ее системы
команд.
Мы предполагаем, что используется стандартный возрастающий
порядок, т. е. элементы массива, определенного описанием
ARRAY А [1:10], размещаются в порядке А [1], А [2], ..., А [10].
Матрицы
Существует несколько способов размещения двумерных массивов.
Обычный способ состоит в хранении их в области данных по строкам
в порядке возрастания, т. е. ( для массива, описанного как
ARRAY А [1:M, 1:N], в порядке
А [1, 1], А [1, 2], ..., А [1, N],
А [2, 1], А [2, 2], ..., А [2, N],
...
А [M, 1], А [M, 2], ..., А [M, N].
Вид последовательности показывает, что элемент А[i, j] находится
в ячейке с адресом ADDRESS ( A[1, 1] ) + (i-1)*N + (j-1) который
можно записать так: ( ADDRESS ( A[1, 1] ) - N - 1 ) + ( i*N + j )
Первое слагаемое является константой, и его требуется вычислить
только один раз. Таким образом, для определения адреса А[i, j]
необходимо выполнить одно умножение и два сложения.
Второй метод состоит в том, что выделяется отдельная область
данных для каждой строки и имеется вектор указателей для этих
областей данных. Элементы каждой строки размещаются в соседних
ячейках в порядке возрастания. Так, описание 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)
