c++ - 使用 std::vector 的稀疏矩阵性能低下

Question

我正在尝试实现 MATLAB 函数的功能 sparse .

在稀疏矩阵中的特定索引处插入一个值，这样:

如果矩阵中已经存在具有相同索引的值，则添加新值和旧值。

否则将新值附加到矩阵。

addNode 函数执行正确，但问题是它非常慢。我在循环中调用此函数大约 100000 次，程序运行时间超过 3 分钟。而 MATLAB 在几秒钟内完成了这项任务。有没有办法优化代码或者用STL算法代替我自己的函数来实现我想要的？

代码:

struct SparseMatNode
{
   int x;
   int y;
   float value;
};

std::vector<SparseMatNode> SparseMatrix;

void addNode(int x, int y, float val)
{
   SparseMatNode n;
   n.x = x;
   n.y = y;
   n.value = val;

   bool alreadyPresent = false;

   int i = 0;
   for(i=0; i<SparseMatrix.size(); i++)
   {
    if((SparseMatrix[i].x == x) && (SparseMatrix[i].y == y))
    {
        alreadyPresent = true;
        break;
    }
   }

   if(alreadyPresent)
   {
    SparseMatrix[i].value += val;
    if(SparseMatrix[i].value == 0.0f)
        SparseMatrix.erase(SparseMatrix.begin + i);
   }
   else
    SparseMatrix.push_back(n);
}

Answer 1

稀疏矩阵通常不会像您尝试的那样存储为三元组 vector 。

MATLAB(以及许多其他库)使用压缩稀疏列 (CSC) 数据结构，这对于静态矩阵非常有效。 MATLAB 函数 sparse 也不会一次构建矩阵一个条目(如您所尝试的那样)- 它需要一个 array 三元组条目并将整个序列打包到 CSC 矩阵中。如果您正在尝试构建静态稀疏矩阵，这就是正确的方法。

如果您想要一个支持有效插入和删除条目的动态稀疏矩阵对象，您可以查看不同的结构 - 可能是三元组的 std::map，或列列表数组- 参见 here有关数据格式的更多信息。

此外，还有很多不错的库。如果您想进行稀疏矩阵运算/分解等 - SuiteSparse是个不错的选择，否则Eigen也有很好的稀疏支持。