c++ - 使用对的矩阵乘法

Question

我正在研究进行矩阵乘法的替代方法。我没有将矩阵存储为二维数组，而是使用了一个 vector ，例如

vector<pair<pair<int,int >,int > > 

存储我的矩阵。我的对 (pair) 中的对存储我的索引 (i,j)，另一个 int 存储给定 (i,j) 对的值。我想我可能会以这种方式实现我的稀疏数组。

问题是当我尝试将该矩阵与自身相乘时。

如果这是一个二维数组实现，我会按如下方式乘以矩阵:

   for(i=0; i<row1; i++)
    {
        for(j=0; j<col1; j++)
        {
          C[i][j] = 0;
         for(k=0; k<col2; k++) 
           C[i][j] += A[i][j] * A[j][k];
      }
    }

有人可以指出使用我的“一对对” vector 实现相同结果的方法吗？

谢谢

Answer 1

到目前为止，您可以在一个位置存储一个值。如果要在矩阵中存储多个非零项，则需要更大结构中的更多对。

map<pair<int, int>, int>将是下一个合乎逻辑的步骤。现在您可以遍历行，因为 first坐标在 map 中更重要的排序顺序。

要遍历列，反转优先级:

typedef pair<int, int> mx_coord;
struct reverse_compare {
    bool operator() (mx_coord const &l, mx_coord const &r) const
        { return l.second < r.second? true :
                 r.second < l.second? false : l.first < r.first; }
};

typedef map< mx_coord, int > matrix;
typedef map< mx_coord, int, reverse_compare > matrix_transpose;

要将 A 乘以 B，转置 B 并遍历 A 和 B，乘以其次要坐标匹配的任何元素，因为排序自然让您可以逐行逐列进行。

转置 B:

matrix_transpose b_t( b.begin(), b.end() ); // complexity: n log n