moltiplicazione matrice utilizzando coppie

Question

Sto cercando di modi alternativi per fare una moltiplicazione di matrici. Invece di memorizzare la matrice come una matrice bidimensionale, sto usando un vettore come

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

per memorizzare la mia matrice. La coppia nel mio pair (coppia) memorizza miei indici (i, j) e gli altri negozi INT Il valore per il dato (i, j) coppia. Ho pensato che avrei potuto avere un po 'di fortuna attuazione mia matrice sparsa in questo modo.

Il problema è quando provo a moltiplicare questa matrice con se stesso.

Se questo fosse un implementazione matrice 2-D, che avrebbe moltiplicato la matrice come segue:

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

Can punto qualcuno un modo per ottenere lo stesso risultato utilizzando il mio vettore di 'coppia di coppie'?

Grazie

Answer 1

Finora è possibile memorizzare un valore in una sola posizione. Se si desidera memorizzare diverse voci diverso da zero nella matrice, avrete bisogno di più coppie di coppie in una struttura più grande.

map<pair<int, int>, int> sarebbe stato il prossimo passo logico. Ora è possibile scorrere sopra le righe perché la coordinata first è più significativo per l'ordinamento del map.

per scorrere le colonne, invertire tale precedenza:

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;

Per A moltiplicare per B, trasposizione B e iterare su A e B, moltiplicando tutti gli elementi le cui coordinate meno significativi corrispondere, come l'ordinamento consente naturalmente di andare riga per riga e colonna per colonna.

Per trasporre B:

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