Массивы с математическим описанием местоположения нефоновых элементов

Специальные массивы

На практике встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших размеров, что для их хранения в полном объеме памяти может быть недостаточно. К таким массивам относятся симметричные и разреженные массивы.

СИММЕТРИЧНЫЕ МАССИВЫ. Двумерный массив, в котором количество строк равно количеству столбцов, называется квадратной матрицей.

Квадратная матрица, у которой элементы, расположенные симметрично относительно главной диагонали, попарно равны друг другу, называется симметричной. Если матрица порядка n симметрична, то в ее физической структуре достаточно отобразить не n², а лишь n*(n+1)/2 её элементов. Иными словами, в памяти необходимо представить только верхний (включая и диагональ) треугольник квадратной логической структуры. Доступ к треугольному массиву организуется таким образом, чтобы можно было обращаться к любому элементу исходной логической структуры, в том числе и к элементам, значения которых хотя и не представлены в памяти, но могут быть определены на основе значений симметричных им элементов.

На практике для работы с симметричной матрицей разрабатываются следующие процедуры для:

а) преобразования индексов матрицы в индекс вектора,

б) формирования вектора и записи в него элементов верхнего треугольника элементов исходной матрицы,

в) получения значения элемента матрицы из ее упакованного представления. При таком подходе обращение к элементам исходной матрицы выполняется опосредованно, через указанные функции.

РАЗРЕЖЕННЫЕ МАССИВЫ. Разреженный массив - массив, большинство элементов которого равны между собой, так что хранить в памяти достаточно лишь небольшое число значений, отличных от основного (фонового) значения остальных элементов.

Различают два типа разреженных массивов:

1) массивы, в которых местоположения элементов со значениями, отличными от фонового, могут быть математически описаны;

2) массивы со случайным расположением элементов.

В случае работы с разреженными массивами вопросы размещения их в памяти реализуются на логическом уровне с учетом их типа.

К данному типу массивов относятся массивы, у которых местоположения элементов со значениями, отличными от фонового, могут быть математически описаны, т.е. в их расположении есть какая-либо закономерность.

Элементы, значения которых являются фоновыми, называют нулевыми; элементы, значения которых отличны от фонового, - ненулевыми. Но нужно помнить, что фоновое значение не всегда равно нулю.

Ненулевые значения хранятся, как правило, в одномерном массиве, а связь между местоположением в исходном, разреженном, массиве и в новом, одномерном, описывается математически с помощью формулы, преобразующей индексы массива в индексы вектора.

На практике для работы с разреженным массивом разрабатываются такие функции:

а) для преобразования индексов массива в индекс вектора;

б) для получения значения элемента массива из ее упакованного представления по двум индексам (строка, столбец);

в) для записи значения элемента массива в ее упакованное представление по двум индексам.

При таком подходе обращение к элементам исходного массива выполняется с помощью указанных функций. Например, пусть имеется двумерная разреженная матрица, в которой все ненулевые элементы расположены в шахматном порядке, начиная со второго элемента. Для такой матрицы формула вычисления индекса элемента в линейном представлении будет следующей:

L=(y*XM+x)/2),

где L - индекс в линейном представлении;

x, y - соответственно строка и столбец в двумерном представлении, нумеруются начиная с нуля

XM - количество элементов в строке и столбце исходной матрицы.

В программном примере 3.1 приведен модуль, обеспечивающий работу с такой матрицей (предполагается, что размер матрицы XM заранее известен).

{===== Программный пример 3.1 =====}

const int XM = …;

int arrp[ XM*XM/2 ];

int NewIndex(int x, int y)

{

return (y*XM + x)/2;

}

bool PutTab(int x, int y, int value)

{

if(!((x+1)%2!=0 && (y+1)%2!=0) ||

!((x+1)%2==0 && (y+1)%2==0))

{

arrp[ NewIndex(x,y) ] = value;

return true;

}

else return false;

}

int GetTab(int x, int y)

{

if(((x+1)%2!=0 && (y+1)%2!=0) ||

((x+1)%2==0 && (y+1)%2==0)) return 0;

else return arrp[ NewIndex(x,y) ];

}

Сжатое представление матрицы хранится в векторе arrp.

Функция NewIndex выполняет пересчет индексов по вышеприведенной формуле и возвращает индекс элемента в векторе arrp.

Функция PutTab выполняет сохранение в сжатом представлении одного элемента с индексами x, y и значением value. Сохранение выполняется только в том случае, если индексы x, y адресуют заведомо ненулевой элемент. Если сохранение выполнено, функция возвращает true, иначе - false.

Для доступа к элементу по индексам двумерной матрицы используется функция GetTab, которая по индексам x, y возвращает выбранное значение. Если индексы адресуют заведомо нулевой элемент матрицы, функция возвращает 0.

В программном примере 3.2 та же задача решается несколько иным способом: для матрицы создается дескриптор - массив desc, который заполняется при инициализации матрицы таким образом, что i -й элемент массива desc содержит индекс первого элемента i -й строки матрицы в ее линейном представлении. Процедура инициализации InitTab включена в число входных точек модуля и должна вызываться перед началом работы с матрицей. Но доступ к каждому элементу матрицы (функция NewIndex) упрощается и выполняется быстрее: по номеру строки y из дескриптора сразу выбирается индекс начала строки и к нему прибавляется смещение элемента из столбца x. Процедуры PutTab и GetTab - такие же, как и в примере 3.1 поэтому здесь не приводятся.

{=====Программный пример 3.2=====}

const int XM = …;

int arrp[ XM*XM/2 ];

int desc[ XM ];

void InitTab()

{

desc[0]=0;

for(int i=1; i<XM; i++) desc[i] = desc[i-1] + XM;

}

int NewIndex(int x, int y)

{

return (desc[y] + x)/2;

}

bool PutTab(int x, int y, int value);

int GetTab(int x, int y)

Дата добавления: 2014-01-07