A.1.6.2 Создание разреженных матриц в файлах Oct

Существует два полезных подхода для создания разреженной матрицы. Первый заключается в создании трех векторов, представляющих индексы строк, индексы столбцов и значения данных, и на основе этих векторов создание матрицы. Второй вариант — создание разреженной матрицы с соответствующим объемом памяти, а затем заполнение значений. Оба метода имеют свои преимущества и недостатки.

Ниже приведен пример создания небольшой разреженной матрицы с использованием первого метода

int nz, nr, nc;
nz = 4, nr = 3, nc = 4;

ColumnVector ridx (nz);
ColumnVector cidx (nz);
ColumnVector data (nz);

ridx(0) = 1; cidx(0) = 1; data(0) = 1;
ridx(1) = 2; cidx(1) = 2; data(1) = 2;
ridx(2) = 2; cidx(2) = 4; data(2) = 3;
ridx(3) = 3; cidx(3) = 4; data(3) = 4;
SparseMatrix sm (data, ridx, cidx, nr, nc);

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

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

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

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

int nz, nr, nc;
nz = 4, nr = 3, nc = 4;
SparseMatrix sm (nr, nc, nz);
sm(0,0) = 1; sm(0,1) = 2; sm(1,3) = 3; sm(2,3) = 4;

Это создаёт ту же матрицу, что и ранее. Опять же, хотя это не строго необходимо, существенно быстрее, если разреженная матрица создаётся, а элементы добавляются в порядке возрастания по столбцам. Причина в том, что при добавлении элементов в конец текущего списка известных элементов, не требуется перемещение какого-либо элемента в матрице для вставки нового элемента; необходимо только обновить индексы столбцов.

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

int nr, nc;
nr = 3, nc = 4;
SparseMatrix sm (nr, nc, 0);
sm(0,0) = 1; sm(0,1) = 2; sm(1,3) = 3; sm(2,3) = 4;

совершенно допустимо. Однако это очень плохая идея, так как при добавлении каждого нового элемента в разреженную матрицу матрица должна запросить больше места и перевыделить память. Это дорогостоящая операция, которая значительно замедлит данный способ создания разреженной матрицы. Возможно создать разреженную матрицу с избыточным объемом памяти, поэтому в данном примере значение nz больше 4 также является допустимым. Недостатком является то, что матрица занимает больше памяти, чем строго необходимо.

Конечно, не всегда возможно знать количество ненулевых элементов до заполнения матрицы. По этой причине дополнительное неиспользуемое хранилище разреженной матрицы может быть удалено после её создания с помощью функции maybe_compress. Кроме освобождения неиспользуемого хранилища, maybe_compress также может удалить нулевые элементы из матрицы. Удаление нулевых элементов из матрицы контролируется установкой аргумента функции maybe_compress на значение true. Однако стоимость удаления нулей высока, так как это подразумевает повторную сортировку элементов. Если это возможно, лучше пользователю избегать добавления ненулевых нулей в первую очередь.

Пример использования функции maybe_compress:

int nz, nr, nc;
nz = 6, nr = 3, nc = 4;

SparseMatrix sm1 (nr, nc, nz);
sm1(0,0) = 1; sm1(0,1) = 2; sm1(1,3) = 3; sm1(2,3) = 4;
sm1.maybe_compress ();   // No zero elements were added

SparseMatrix sm2 (nr, nc, nz);
sm2(0,0) = 1; sm2(0,1) = 2; sm(0,2) = 0; sm(1,2) = 0;
sm1(1,3) = 3; sm1(2,3) = 4;
sm2.maybe_compress (true);  // Zero elements were added

Использование функции maybe_compress следует избегать, если это возможно, так как это замедлит создание матрицы.

Третий способ создания разреженной матрицы заключается в непосредственной работе с данными в сжатом формате строк. Пример этого расширенного метода может быть

octave_value arg;
…
int nz, nr, nc;
nz = 6, nr = 3, nc = 4;   // Assume we know the max # nz
SparseMatrix sm (nr, nc, nz);
Matrix m = arg.matrix_value ();

int ii = 0;
sm.cidx (0) = 0;
for (int j = 1; j < nc; j++)
  {
    for (int i = 0; i < nr; i++)
      {
        double tmp = m(i,j);
        if (tmp != 0.)
          {
            sm.data(ii) = tmp;
            sm.ridx(ii) = i;
            ii++;
          }
      }
    sm.cidx(j+1) = ii;
 }
sm.maybe_compress ();  // If don't know a priori the final # of nz.

что, вероятно, является наиболее эффективным способом создания разреженной матрицы.

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

octave_value arg;
…
int nz, nr, nc;
nz = 6, nr = 3, nc = 4;   // Guess the number of nz elements
SparseMatrix sm (nr, nc, nz);
Matrix m = arg.matrix_value ();

int ii = 0;
sm.cidx (0) = 0;
for (int j = 1; j < nc; j++)
  {
    for (int i = 0; i < nr; i++)
      {
        double tmp = m(i,j);
        if (tmp != 0.)
          {
            if (ii == nz)
              {
                nz += 2;   // Add 2 more elements
                sm.change_capacity (nz);
              }
            sm.data(ii) = tmp;
            sm.ridx(ii) = i;
            ii++;
          }
      }
    sm.cidx(j+1) = ii;
 }
sm.maybe_compress ();  // If don't know a priori the final # of nz.

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