La multiplicación de matrices utilizando pares

Question

Estoy buscando en formas alternativas para hacer una multiplicación de matrices. En lugar de almacenar mi matriz como una matriz de dos dimensiones, estoy usando un vector tal como

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

para almacenar mi matriz. El par dentro de mi par (par) almacena mis índices (i, j) y las otras tiendas int El valor para el (i, j) par dado. Yo pensé que podría tener un poco de suerte la implementación de mi matriz dispersa de esta manera.

El problema es cuando intento para multiplicar esta matriz con sí mismo.

Si este era un 2-d array aplicación, habría multiplicado la matriz como sigue:

   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 momento alguien encontrar una manera de conseguir el mismo resultado usando mi vectorial de 'par de pares'?

Gracias

Answer 1

Hasta el momento se puede almacenar un valor en un solo lugar. Si desea almacenar varios elementos no nulos en la matriz, se necesita más pares de pares en una estructura mayor.

map<pair<int, int>, int> sería el siguiente paso lógico. Ahora se puede iterar sobre filas debido a coordinar el first es más significativo en la forma de ordenación de la map.

Para iterar sobre columnas, revertir esa precedencia:

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;

Para una multiplicación por B, transpuesta B y iterar sobre A y B, multiplicando los elementos cuyas coordenadas menos significativos coincidir, como el ordenamiento permite, naturalmente, ir línea por línea y columna por columna.

Para transponer B:

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