3

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

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

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

谢谢

4

1 回答 1

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
于 2010-04-06T04:32:54.667 回答