Как я могу умножить две матрицы, если я храню только ненулевые элементы в списке<list<pair<int,double>>>?
Так у меня появился проект по структурам данных и алгоритмам. Мне в основном нужно разработать матрицу класса со следующими атрибутами:
- list<list<pair<int,double>>>, (В котором только ненулевые элементы Matrix. Значение определенного элемента хранится как второй аргумент пары, а первый аргумент пары представляет собой фактический столбец, в котором этот элемент находится в исходной матрице)
- vector< int> rows, (rows[i] — представляет фактическую строку для каждого списка в списке списков выше, соответственно)
- Фактическое количество строк,
- Фактическое количество столбцов.
В моем проекте до сих пор я разработал специальные конструкторы, сложение и вычитание матриц и т. д. Единственное, что я не могу сделать, это умножить два экземпляра класса Matrix, то есть я не могу разработать оператор * для класса Matrix.
Объяснение проблемы:
Предполагая, что у меня есть следующие два экземпляра класса Matrix:
Экземпляр А:
list<list<pair<int,double>>>: {{{10,5},{40,15}},{{50,25}},{{80,35}}}
vector<int>: {2,10,70};
actual number of rows: 100
actual number of columns: 100
Экземпляр Б:
list<list<pair<int,double>>>: {{{1,6},{2,5},{3,7}},{{3,4}},{{80,1}}}
vector<int>: {1,2,33};
actual number of rows: 100
actual number of columns: 100
Очевидно, что для этих матриц определено умножение, так как количество столбцов матрицы A равно количеству строк матрицы B. У меня возникли проблемы с поиском правильного алгоритма умножения этих матриц. Может кто-нибудь написать короткими строками, что может быть одним из алгоритмов их умножения.
Спасибо за ответ, выполнение умножения, очевидно, является самой сложной частью, потому что я не могу использовать ничего, кроме заданных атрибутов.
Если вы покажете свой код (минимальный воспроизводимый пример ), возможно, кто-нибудь сможет вам в этом помочь.
Я не могу разработать оператор*" мне непонятно, почему вы не можете этого сделать. Вы хотите сказать, что это дает неправильный ответ? Вы хотите сказать, что не знаете синтаксис объявления? Я предполагаю, что вы где-то застряли, но если моя догадка верна, вы не упомянули, где вы застряли.
Я думаю, что с учетом атрибутов класса любой, кто действительно знает, как это решить, может ответить без проблем.
в то время как люди могли бы строить догадки, было бы намного проще ответить с минимально воспроизводимым примером. Чем именно вы застряли? Алгоритм? Синтаксис? Жук?
У меня возникли проблемы с поиском правильного алгоритма для этого.
ссылка: mathsisfun.com/алгебра/matrix-multipliing.html
@SMAJKE вы всегда можете отредактировать этот вопрос, чтобы уточнить его. Как сейчас написано, люди угадывают, в чем заключается ваш реальный вопрос/проблема.
У меня нет проблем ни с пониманием матричного умножения в целом, ни с реализацией его с матрицами, в которых я также могу хранить нулевые значения. Вот что делает эту проблему сложной, не сохраняются нулевые элементы.
Алгоритм, который вы ищете, умножает разреженные матрицы,
Ответы 1
Основная идея состоит в том, чтобы иметь удобный примитив для установки/получения значения в позиции (i, j) матрицы, ее количества строк и ее количества столбцов.
Для простоты я заменил в следующем коде ваш верхний список вектором (это более эффективно, поскольку у вас есть произвольный доступ к i-му значению):
#include <cassert>
#include <iostream>
#include <list>
#include <vector>
using namespace std;
class Matrix {
private:
vector<list<pair<unsigned, double>>> data;
unsigned m;
unsigned n;
public:
Matrix(unsigned m, unsigned n):
m(m),
n(n),
data(m)
{}
inline unsigned num_rows() const {
return m;
}
inline unsigned num_columns() const {
return n;
}
double get(unsigned i, unsigned j) const {
for (pair<unsigned, double> p : data[i]) {
if (p.first == j) return p.second;
}
return 0.0;
}
void set(unsigned i, unsigned j, double v) {
for (pair<unsigned, double> p : data[i]) {
if (p.first == j) {
p.second = v;
return;
}
}
if (v) {
data[i].push_back(make_pair(j, v));
}
}
};
Matrix operator * (const Matrix & a, const Matrix & b) {
unsigned m = a.num_rows(),
n = b.num_columns(),
k_max = a.num_columns();
assert (a.num_columns() == b.num_rows());
Matrix c(m, n);
for (unsigned i = 0; i < m; i++) {
for (unsigned j = 0; j < n; j++) {
double value = 0;
for (unsigned k = 0; k < k_max; k++) {
value += a.get(i, k) * b.get(k, j);
}
if (value) c.set(i, j, value);
}
}
return c;
}
ostream & operator << (ostream & out, const Matrix & a) {
for (unsigned i = 0; i < a.num_rows(); i++) {
for (unsigned j = 0; j < a.num_columns(); j++) {
out << a.get(i, j) << "\t";
}
out << endl;
}
return out;
}
int main() {
Matrix a(2, 3), b(3, 1);
for (unsigned i = 0; i < a.num_rows(); i++) {
for (unsigned j = 0; j < a.num_columns(); j++) {
a.set(i, j, 10 * i + j);
}
}
for (unsigned i = 0; i < b.num_rows(); i++) {
for (unsigned j = 0; j < b.num_columns(); j++) {
b.set(i, j, 10 * (i + 1));
}
}
Matrix c = a * b;
cout << "a:" << endl << a << endl
<< "b:" << endl << b << endl
<< "c:" << endl << c << endl
;
return 0;
}
Результат:
a:
0 1 2
10 11 12
b:
10
20
30
c:
80
680
Чувак, ты легенда, как только я увидел эти функции get и set, я понял, какой должна быть реализация operator*. Большое спасибо <3
Matrix& operator*=(const Matrix& rhs) { perform multiplication; return *this; }иMatrix operator*(const Matrix& lhs, const Matrix& rhs) { Matrix rv(lhs); rv *= rhs; return rv; }было бы началом.