更有效的稀疏矩阵元素访问器

Question

我用成员写了一个小的稀疏矩阵类:

std::map<int,std::map<int,double> > sm;

下面的方法是我用来访问矩阵元素的函数,如果通过迭代器不可能的话:

double matrix::operator()(int r,int c) const
{
    std::map<int,std::map<int,double> >::const_iterator i = sm.find(r);
    if(i==sm.end()) { return 0.0; }
    std::map<int,double>::const_iterator j = i->second.find(c);
    if(j==i->second.end()) { return 0.0; }
    return j->second;
}

仍然需要经常调用此函数.有人知道如何改进这个功能吗？谢谢你.

Answer 1

如果您要编写自己的代码而不是使用库,那么此更改可能会显着提高性能:

std::map<std::pair<int,int>, double> sm;

为了进一步增加,你可以去散列容器:

std::unordered_map<std::pair<int,int>, double> sm;

(使用tr1,boost或C++ 0x)

编辑:在第一种情况下你可以row像这样迭代:

for(auto& cell : make_pair(
    sm.lower_bound(make_pair(row, 0)), sm.lower_bound(make_pair(row+1, 0))))
{ ... }

我认为如果使用Boost.MultiIndex,可以通过使用适当的函子调用equal_range来完成上述操作.

一切都:

for(auto& cell : sm)
{ ... }

要迭代一列,您需要分别搜索每个单元格.请注意,您的数据结构也不提供此操作.