c++ - 更高效的稀疏矩阵元素访问器

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)
{ ... }

要遍历列，您需要分别搜索每个单元格。请注意，您的数据结构也不提供此操作。