4

我正在尝试实现 MATLAB function 的功能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);
}
4

5 回答 5

5

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

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

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

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

于 2012-11-19T07:44:01.077 回答
3

稀疏矩阵通常以压缩稀疏行 (CSR) 或压缩稀疏列 (CSC，也称为 Harwell-Boeing) 格式存储。MATLAB 默认使用 CSC、IIRC，而大多数稀疏矩阵包倾向于使用 CSR。

无论如何，如果这是用于生产用途而不是学习练习，我建议使用支持稀疏矩阵的矩阵包。在 C++ 世界中，我最喜欢的是Eigen。

于 2012-11-19T07:40:54.327 回答
2

您是否尝试过对稀疏节点向量进行排序？每次添加节点时，执行线性搜索都会变得很昂贵。您可以就地插入并始终执行二进制搜索。

于 2012-11-19T07:40:11.637 回答
2

第一个认为突出的是您正在实现自己的功能来查找元素：这就是std::find目的。所以，而不是：

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;
  }
}

你应该写：

auto it = std::find(SparseMatrix.begin(), SparseMatrix().end(), Comparer);

whereComparer是一个比较两个SparseMatNode对象的函数。

但主要的改进将来自使用适当的容器。而不是std::vector，使用关联容器会更好。这样，找到一个元素将只具有O(logN)复杂性而不是O(N). 你可以稍微修改你的SparseMatNode类如下：

typedef std::pair<int, int> Coords;
typedef std::pair<const Coords, float> SparseMatNode;

当然，您可以在类中覆盖此 typedef 以提供更好的接口。

进而：

std::unordered_map<Coords, float> SparseMatrix;

这样你就可以使用：

auto it = SparseMatrix.find(std::make_pair(x, y));

更有效地查找元素。

于 2012-11-19T07:54:54.137 回答
-1

因为稀疏矩阵可能很大并且需要压缩，你可以使用std::unordered_map. 我假设矩阵索引 (x和y) 始终为正。

#include <unordered_map>

const size_t MAX_X =  1000*1000*1000;
std::unordered_map <size_t, float> matrix;

void addNode (size_t x, size_t y, float val)
{
   size_t index = x + y*MAX_X;
   matrix[index] += val;      //this function can be still faster
   if (matrix[index] == 0)    //using find() / insert() methods
       matrix.erase(index);
}

如果std::unordered_map在您的系统上不可用，您可以尝试std::tr1::unordered_map或stdext::hash_map...

如果您可以使用更多内存，请使用double而不是float，这将提高您的处理速度。

于 2012-11-19T07:34:21.847 回答