c++ - 对于 SparseMatrix 实现，我们能做的最好的是什么？

Question

我使用的是 Eigen 矩阵框架和 SparseVector 库。我遇到了性能问题，我都需要它是稀疏 vector 点积。所以我推出了自己的 SparseMatrix 实现，希望它能以某种方式更快一点:

一些示例代码:

#include <map>
using namespace std ;

struct SparseMatrix
{
  map<int, Vector> vals ;

  Vector dot( SparseMatrix& o )
  {
    SparseMatrix *LS, *RS ;

    // iterate over the smaller of the 2 
    if( vals.size() < o.vals.size() )
    {
      // walk vals
      LS = this ;
      RS = &o ;
    }
    else
    {
      LS = &o ;
      RS = this ;
    }

    // walk LS
    Vector sum = 0 ;

    for( map<int,Vector>::iterator LSIter = LS->vals.begin() ; LSIter != LS->vals.end() ; ++LSIter )
    {
      const int& key = LSIter->first ;

      // use the key, see if RS has a similar entry.
      map<int,Vector>::iterator RSIter = RS->vals.find( key );
      if( RSIter != RS->vals.end() )
        sum += RSIter->second * LSIter->second ;
    }

    return sum ;
  }
} ;

所以 2 个 vector 的点积，假设有如下条目:

+---------------+| vec 1         || index   value ||   2      18   ||   7       4   ||  18      33   |+---------------++---------------+| vec 2         || index   value ||   2       1   ||  15      87   ||  21      92   |+---------------+

点积是 18。

因此，如您所见，我使用 std::map 进行元素查找，以查看一个 vector 中的元素是否在另一个 vector 中。

由于我只使用整数索引和一维数组，有什么方法可以加快查找速度吗？我的稀疏矩阵乘法仍然是一个瓶颈(我的代码的性能只比 Eigen 快一点点)

Answer 1

有一个 vector 对:索引 -> 值，按索引排序。然后一次迭代两个 vector 。如果你有两个相同的索引，将值相乘，将其添加到结果中并转到两个 vector 中的下一对。否则在 pair 的第一个元素较小的 vector 上增加迭代索引。

当然，假设您不经常修改数据。

即在伪代码中:

for i = 0, j = 0; i < vec1.size && j < vec2.size:
    if vec1[i].first == vec2[j].first:
        result += vec1[i++].second * vec2[j++].second
    elif vec1[i].first < vec2[j].first:
        i++
    else
        j++