c++ - 为什么 boost ublas 中的 compress_matrix 会为非零元素分配更多的内存？

Question

我深入研究了 boost ublas 代码，发现 compressed_matrix 中内存分配的 ublas 实现并不像 CSC 或 CSR 中那样标准。

有一行引起了麻烦，即non_zeros = (std::max) (non_zeros, (std::min) (size1_,size2_)); 在私有(private) restrict_capactiy 方法中。

这是否意味着如果我创建一个稀疏矩阵，在 boost ublas 中分配的非零数将始终大于 min(nrow, ncol)？

我用下面的代码来演示这个问题。输出将在 compressed_matrix 中分配的 vector 的未使用部分中包含零。

typedef boost::numeric::ublas::compressed_matrix<double, boost::numeric::ublas::column_major,0,std::vector<std::size_t>, std::vector<double> > Matrix;
long nrow = 5;
long ncol = 4;
long nnz = 2;

Matrix m(nrow, ncol, nnz);
cout<<"setting"<<endl;
m(1,2) = 1.1;
m(2,2) = 2.1;
    for(int i=0;i<m.index1_data().size();i++)
{
    cout<<"ind1 -"<<i<<" "<<m.index1_data()[i]<<endl;
}

for(int i=0;i<m.index2_data().size();i++)
{
    cout<<"ind2 -"<<i<<" "<<m.index2_data()[i]<<endl;
}

for(int i=0;i<m.value_data().size();i++)
{
    cout<<"val  -"<<i<<" "<<m.value_data()[i]<<endl;
}

Answer 1

也许这是考虑到某些用例的性能设计选择。

想法是，当填充 compressed_matrix 时，可能会尝试尽量减少维护索引/值数组的数组的重新分配。如果从 0 分配的空间开始，它将很快以推测方式重新分配一次(例如，每次超过分配的空间时保留两倍的空间，如 std::vector 所做的那样)。

因为这个想法是取消密集矩阵的 $N^2$ 缩放。一个很好的猜测是，在稀疏矩阵中，您将使用 $N^2$ 中或多或少的 $N$ 个元素。如果您使用超过 $N$，那么重新分配会在某个时候发生，但次数不会那么多。但是你可能会遇到无论如何都最好切换到密集矩阵的情况。

更令人惊讶的是它覆盖了传递的值。但是，上述内容仍然适用。