使用對的矩陣乘法

Question

我正在尋找替代方法來執行矩陣乘法。而不是將我的矩陣存儲爲二維數組，我使用的矢量如

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

存儲我的矩陣。我的配對（對）中的這對配對存儲了我的索引（i，j），其他int存儲了給定（i，j）配對的值。我想我可能會用這種方式實現我的稀疏數組。

問題是，當我試圖乘以這個矩陣與自己。

如果這是一個2-d數組實現，我會成倍的增加矩陣如下：

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

可有人指出的方式使用我的「對對」載體來實現相同的結果？

謝謝

Answer 1

到目前爲止，您可以在一個位置存儲一個值。如果你想在矩陣中存儲幾個非零項，你將需要更多結構對中的更多對。

map<pair<int, int>, int>將是下一個邏輯步驟。現在，您可以遍歷行，因爲的排序順序中first座標更重要。

遍歷列扭轉的優先級：

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和迭代A和B，乘以其-顯著少座標匹配的任何元件，如排序自然讓你逐行並逐列。

要轉B：

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