Разреженные массивы со случайным расположением элементов

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

0 0 6 0 9 0 0 Пусть есть матрица А размерности 5*7, в которой

2 0 0 7 8 0 4 из 35 элементов только 10 отличны от нуля.

10 0 0 0 0 0 0

0 0 12 0 0 0 0

0 0 0 3 0 0 5

ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ ПОСЛЕДОВАТЕЛЬНОГО РАЗМЕЩЕНИЯ. Один из основных способов хранения подобных разреженных матриц заключается в запоминании ненулевых элементов в одномерном массиве и идентификации каждого элемента массива индексами строки и столбца, как на рис. 3.5, а.

Доступ к элементу массива A с индексами i и j выполняется выборкой индекса i из вектора ROW, индекса j из вектора COLUM и значения элемента из вектора A. Слева указан индекс k векторов, наибольшее значение которого определяется количеством нефоновых элементов. Отметим, что элементы массива обязательно запоминаются в порядке возрастания номеров строк.

Более эффективное представление, с точки зрения требований к памяти и времени доступа к строкам матрицы, показано на рис. 3.3,б. Вектор ROW уменьшен, количество его элементов соответствует числу строк исходного массива A, содержащих нефоновые элементы. Этот вектор получен из вектора ROW рис. 3.3,а так, что его i -й элемент является индексом k для первого нефонового элемента i -й строки.

Рис. 3. 3. Последовательное представление разреженных матриц

Представление матрицы А, данное на рис. 3.5, сокращает требования к объему памяти более чем в 2 раза. Для больших матриц экономия памяти очень важна. Способ последовательного распределения имеет также то преимущество, что операции над матрицами могут быть выполнены быстрее, чем это возможно при представлении в виде последовательного двумерного массива, особенно если размер матрицы велик.

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