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 ();   // 没有添加零元素

SparseMatrix sm2 (nr, nc, nz);
sm2(0,0) = 1; sm2(0,1) = 2; sm2(0,2) = 0; sm2(1,2) = 0;
sm2(1,3) = 3; sm2(2,3) = 4;
sm2.maybe_compress (true);  // 添加了零元素

如果可能的话，应避免使用 maybe_compress 函数，因为它会降低矩阵创建的速度。

创建稀疏矩阵的第三种方法是直接使用压缩行格式操作数据。这种高级技术的一个示例如下：

octave_value arg;
...
int nz, nr, nc;
nz = 6, nr = 3, nc = 4;   // 假设我们知道最大非零元素数量
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 ();  // 如果事先不知道最终的非零元素数量

这可能是创建稀疏矩阵最有效的方法。

最后，有时可能会出现最初分配的存储空间不足以完全存储稀疏矩阵的情况。因此，存在 change_capacity 方法用于重新分配稀疏内存。上述示例可以修改为：

octave_value arg;
...
int nz, nr, nc;
nz = 6, nr = 3, nc = 4;   // 猜测非零元素的数量
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;   // 增加2个元素空间
                sm.change_capacity (nz);
              }
            sm.data(ii) = tmp;
            sm.ridx(ii) = i;
            ii++;
          }
      }
    sm.cidx(j+1) = ii;
 }
sm.maybe_compress ();  // 如果事先不知道最终的非零元素数量

请注意，增加和减少稀疏矩阵中非零元素的数量都是昂贵的操作，因为这涉及到内存的重新分配。此外，因为矩阵的部分数据（虽然不是全部）会同时存在新旧两份副本，所以需要额外的内存。因此，如果可能的话，应避免改变容量。