Multiplication de matrices utilisant des paires

Question

Je suis à la recherche d'autres façons de faire une multiplication matricielle. Au lieu de stocker ma matrice comme un tableau à deux dimensions, j'utilise un vecteur tel que

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

pour stocker ma matrice. La paire dans ma paire (paire) stocke mes indices (i, j) et l'autre int stocke la valeur pour la paire donnée (i, j). Je pensais que j'aurais peut-être de la chance en implémentant ma matrice éparpillée de cette façon.

Le problème est lorsque j'essaie de multiplier cette matrice avec elle-même.

Si cela était une mise en œuvre du tableau 2-d, aurait multiplié la matrice comme suit:

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

Quelqu'un peut-il indiquer un moyen d'obtenir le même résultat en utilisant mon vecteur de « paire de paires » ?

Merci

Answer 1

Jusqu'à présent, vous pouvez stocker une valeur à un emplacement. Si vous voulez stocker plusieurs entrées non nulles dans la matrice, vous aurez besoin de plusieurs paires de paires dans une structure plus grande.

map<pair<int, int>, int> serait la prochaine étape logique. Vous pouvez maintenant itérer sur les lignes car la coordonnée first est plus significative dans l'ordre de tri map.

pour itérer sur les colonnes, inverser cette priorité:

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; 

Pour multiplier A par B, transposer B et itérer sur A et B, en multipliant les éléments dont le jeu de coordonnées moins importantes, comme la commande permet naturellement vous allez ligne par ligne et colonne par colonne.

Pour transposent B:

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