Умножение матриц с использованием пар - PullRequest
Новая
       17

Умножение матриц с использованием пар

3 голосов
/ 06 апреля 2010

Я ищу альтернативные способы умножения матриц.Вместо того, чтобы хранить свою матрицу в виде двумерного массива, я использую вектор, такой как 

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

, для хранения моей матрицы.Пара внутри моей пары (pair) хранит мои индексы (i, j), а другая int хранит значение для данной пары (i, j).Я подумал, что мне немного повезло, если бы я так реализовал мой разреженный массив.

Проблема в том, что я пытаюсь умножить эту матрицу на себя.

Если бы это была реализация двумерного массива, я бы умножил матрицу следующим образом: 

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

Может кто-нибудь указать способ достижения того же результата, используя мой вектор 'пара пар '?

Спасибо

1 Ответ

1 голос
/ 06 апреля 2010

Пока вы можете хранить одно значение в одном месте. Если вы хотите сохранить несколько ненулевых записей в матрице, вам потребуется больше пар пар в более крупной структуре.

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;

Чтобы умножить A на B, транспонировать B и выполнить итерации по A и B, умножая любые элементы, чьи менее значимые координаты совпадают, поскольку упорядочение, естественно, позволяет переходить по строкам и столбцам за столбцами.

Для транспонирования B: 

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