4

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

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

仍然需要经常调用此函数。有人知道如何改进此功能吗？提前谢谢。

4

2 回答 2

6

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

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

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

于 2010-10-01T19:22:48.013 回答
1

您可能会讨厌这个，但是对于矩阵的以下（为了显示目的很小）行：

1 0 0 5 9 0 0 0

您可以有一个位数组（在这种情况下为 8 位），其中设置或清除每个位以反映矩阵中该位置是否存在非零或零。

然后，您只需将非零数字存储在一个打包在一起的常规数组中，例如：

{ 1, 5, 9 }

和二进制标志

0x98 // 二进制 1001 1000

要遍历矩阵行，您只需使用位操作来循环位数组：

while (! /* not at the end of the bit array */ ) {
    f = get_next_from_bit_array();  // This is just bitwise shift and bitwise & 
    if (!f) {
       val = 0;
    } else {
       val = compressed_row[i];
       i++;
    }
    do_action(val);
}

我这里的代码只是为了演示，不是很 C++，但我希望你能明白。

使用位数组将允许您检查稀疏行的小得多的内存区域，这意味着更少的内存访问和更好的缓存局部性。

如果您正在使用的矩阵非常稀疏，那么您也可以将其扩展到另一个维度（具有稀疏的行数组），但是您将整行都留空的可能性可能很低。

于 2010-10-01T20:14:20.883 回答