使用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

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

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

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

此外,还有很多好的图书馆.如果你想做稀疏矩阵运算/因子分析等 - SuiteSparse是一个不错的选择,否则Eigen也有很好的稀疏支持.