쌍을 사용하는 행렬 곱셈

Question

행렬 곱셈을 수행하는 다른 방법을 찾고 있습니다. 행렬을 2 차원 배열로 저장하는 대신 내 행렬을 저장하려면

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

과 같은 벡터를 사용하고 있습니다. 내 쌍 (pair) 내의 쌍은 my index (i, j)를 저장하고 다른 int는 주어진 (i, j) 쌍의 값을 저장합니다. 이런 식으로 내 희소 배열을 구현하는 행운이 있을지도 모른다고 생각했습니다.

문제는이 행렬에 자체를 곱하려고 할 때입니다. 이 2 차원 어레이를 구현했다면 다음

는 I 행렬을 곱한 것이다 :

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

지금까지 한 위치에 하나의 값을 저장할 수 있습니다. 행렬에 여러 개의 0이 아닌 항목을 저장하려면 더 큰 구조에서 쌍의 쌍이 더 필요합니다.

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; 

는 B에 의해 곱셈 B 트랜스와 A와 B를 반복 :

는 반대로 열을 통해 그 우선 순위를 반복하려면 당신은 줄 단위로 그리고 열 단위로 간다.

B는 트랜스하려면 :

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