Optimierung des Matrixmultiplikationsalgorithmus
Ich habe meine eigene Version des Algorithmus implementiert, um zwei Matrizen miteinander zu multiplizieren, und ich brauche jemanden, der weiß, was er tut, um zu sehen, ob es etwas gibt, das optimaler gemacht werden kann. Ich bin auch sehr daran interessiert zu verstehen, wie ich es robust machen kann, damit es nicht abstürzt, wenn nicht rechteckige Matrizen als Argument übergeben werden, dh eine Matrix, die eine ungerade Anzahl von Elementen in verschiedenen VdS enthält.
Ich interessiere mich besonders für die Funktion matrixDotim folgenden Code. Alles andere ist nur zu zeigen, wie ich es in meinem Projekt verwende.
#include "iostream"
#include <vector>
#define LOG(m) std::cout << m << std::endl
struct Vd
{
std::vector<double> v;
};
struct Md
{
std::vector<Vd> m;
//fill matrix with num
void fill(unsigned const int rows, unsigned const int cols, const double num)
{
m.clear();
for (unsigned int i = 0; i < rows; i++)
{
Vd tempVec;
for (unsigned int j = 0; j < cols; j++)
{
tempVec.v.push_back(num);
}
m.push_back(tempVec);
}
}
friend std::ostream& operator << (std::ostream& out, const Md& mat)
{
out << "[" << std::endl << std::endl;
for (unsigned int i = 0; i < mat.m.size(); i++)
{
out << "[";
for (unsigned int j = 0; j < mat.m[i].v.size(); j++)
{
if (j % mat.m[i].v.size() == mat.m[i].v.size() - 1)
out << mat.m[i].v[j] << "]" << std::endl << std::endl;
else
out << mat.m[i].v[j] << ", ";
}
}
out << "]" << std::endl;
return out;
}
};
inline void matrixDot(const Md& m1, const Md& m2, Md& outm)
{
if (m1.m[0].v.size() && m2.m.size())
if (m1.m[0].v.size() != m2.m.size())
{
LOG("Shape mismatch: " << "matrix1 columns: " << m1.m[0].v.size() << ", " << "matrix2 rows: " << m2.m.size());
throw std::exception();
}
unsigned int m1x = 0; unsigned int m1y = 0; unsigned int m2y = 0; //m2x = m1y
while (outm.m.size() < m1.m.size())
{
Vd tempv;
while (tempv.v.size() < m2.m[0].v.size())
{
double total = 0.0;
while (m1x < m1.m[0].v.size())
{
total += m1.m[m1y].v[m1x] * m2.m[m1x].v[m2y];
m1x++;
}
tempv.v.push_back(total);
m1x = 0;
m2y < m2.m[0].v.size() - 1 ? m2y++ : m2y = 0;
}
m1y < m1.m.size() - 1 ? m1y++ : m1y = 0;
outm.m.push_back(tempv);
}
}
int main()
{
Md mat1;
mat1.fill(5, 2, 1.0);
Md mat2;
mat2.fill(2, 6, 2.0);
Md mat3;
matrixDot(mat1, mat2, mat3);
std::cout << mat3;
}
Antworten
Ich sehe einige Dinge, die Sie möglicherweise verwenden möchten, um Ihren Code zu verbessern.
Verwenden Sie usinggegebenenfalls
Der Code enthält derzeit Folgendes:
struct Vd
{
std::vector<double> v;
};
Dies wird wahrscheinlich besser so ausgedrückt:
using Vd = std::vector<double>;
Also jetzt, anstatt dies zu schreiben:
out << mat.m[i].v[j] << ", ";
Wir können diese sauberere Syntax verwenden:
out << mat.m[i][j] << ", ";
Verstehen Sie die Header-Include-Pfade
Es gibt einen subtilen Unterschied zwischen #include "iostream"und #include <iostream>. Obwohl die Implementierung definiert ist, suchen die meisten Compiler-Implementierungen zuerst lokal in Anführungszeichen (z. B. im aktuellen Verzeichnis) und durchsuchen dann das System mit Verzeichnissen, wenn dies fehlschlägt. Die spitze Klammerform sucht normalerweise in System-Include-Verzeichnissen. Weitere Informationen finden Sie in dieser Frage . Aus diesem Grund sollte dieser Code wahrscheinlich verwenden #include <iostream>.
Nicht verwenden, std::endlwenn Sie es nicht wirklich brauchen
Der Unterschied zwischen std::endlund '\n'besteht darin, dass '\n'nur ein Zeilenumbruchzeichen ausgegeben wird, während std::endlder Stream tatsächlich geleert wird . Dies kann in einem Programm mit vielen E / A zeitaufwändig sein und wird selten tatsächlich benötigt. Es ist am besten, es nur zu verwenden, std::endlwenn Sie einen guten Grund haben, den Stream zu leeren, und es wird für einfache Programme wie dieses nicht sehr oft benötigt. Das Vermeiden der Gewohnheit, std::endlwann '\n'dies der Fall ist, zahlt sich in Zukunft aus, wenn Sie komplexere Programme mit mehr E / A schreiben und die Leistung maximiert werden muss.
Verwenden Sie gegebenenfalls Standardfunktionen
Anstatt das zu schreiben, ostream& operator<<wie Sie es haben, wäre eine nette Alternative, Folgendes zu verwenden std::copyund zu std::experimental::ostream_joinermögen:
friend std::ostream& operator << (std::ostream& out, const Md& mat)
{
out << "[\n";
for (const auto& row : mat.m) {
out << "\t[";
std::copy(row.begin(), row.end(), std::experimental::make_ostream_joiner(out, ", "));
out << "]\n";
}
return out << "]\n";
}
Bevorzugen Sie Rückgabewerte gegenüber Ausgabeparametern
Es erscheint viel logischer, matrixDoteine neue Matrix zurückzugeben, als den dritten Parameter als Ausgabeparameter zu verwenden. Siehe F.20 für weitere Details.
Betrachten Sie eine alternative Darstellung
Dieser Code ist etwas zerbrechlich, dass sowohl das Mdund Vdwie umgesetzt struct, mit allen Mitgliedern der Öffentlichkeit. Schlimmer ist, dass wir ein gezacktes Array haben könnten, in dem nicht jede Zeile die gleiche Anzahl von Elementen enthält. Dies wird wahrscheinlich zu nichts Schönem führen. Aus diesen beiden Gründen würde ich vorschlagen, ein classund ein einzelnes vectorzu verwenden, um alle Elemente zu speichern. In dieser Frage finden Sie einige Ideen und Ratschläge dazu. Sie können auch std::valarrayeinen zugrunde liegenden Typ betrachten.
Stellen Sie eine vollständige Klassenimplementierung bereit
Zusätzlich zu einem Konstruktor, der std::initializer_listArgumente verwendet, würde ich auch einige andere Operatoren vorschlagen, z. B. operator==für diese Klasse.
Ich muss zugeben, dass ich ein bisschen verwirrt bin, du hast die harten Teile gemacht und hast eine Frage zu den einfachen Teilen? Ich könnte Ihre Frage falsch verstehen.
Ich bin auch sehr daran interessiert zu verstehen, wie ich es robust machen kann, damit es nicht abstürzt, wenn nicht rechteckige Matrizen als Argument übergeben werden, dh eine Matrix mit einer ungeraden Anzahl von Elementen in verschiedenen Vds.
Sie können überprüfen, ob Sie eine gut geformte Matrix haben
inline bool isValid(const Md& mat)
{
if (mat.m.size())
{
int size = mat.m[0].v.size();
for (int i = 1; i < mat.m.size(); i++) {
if (size != mat.m[i].v.size())
{
return false;
}
}
}
return true;
}
und Einbindung in die matrixDotValidierungsfunktion, ähnlich der Formvalidierung, die Sie gerade haben
if (m1.m[0].v.size() && m2.m.size())
if (m1.m[0].v.size() != m2.m.size())
{
LOG("Shape mismatch: " << "matrix1 columns: " << m1.m[0].v.size() << ", " << "matrix2 rows: " << m2.m.size());
throw std::exception();
}
if (!isValid(m1))
{
LOG("Invalid matrix :: " << std::endl);
std::cout << m1;
throw std::exception();
}
if (!isValid(m2))
{
LOG("Invalid matrix :: " << std::endl);
std::cout << m2;
throw std::exception();
}
Alle Optimierungen, die mir in den Sinn kommen, werden verwendet, std::arrayanstatt die std::vectorZeilen- und Spaltenlängen zum Zeitpunkt der Erstellung zu kennen.
Persönlich würde ich die Md-Struktur (Klasse) so erweitern, dass sie die Matrix vollständig einkapselt. Es hätte:
-> Mitgliedsvariablen für:
The number of rows and columns.
Vector to hold the data. (Consider one dimensional array here).
-> Konstruktor, mit dem eine Matrix mit der richtigen Größe erstellt werden kann (Zeilen, Spalten).
This would allow you to use vector resize and reserve which will give you
a more performant implementation, especially if the matrices are re-used.
So avoid using push_back and instead set values directly.
-> Funktionen abrufen, um die Anzahl der Zeilen / Spalten abzurufen
-> Get / Set-Funktionen zum Abrufen / Setzen von Matrixdatenwerten.
Get/Set functions implement bounds checking.
Ich würde dann eine mathMatrix-Klasse ableiten, die die Matrixmultiplikationsfunktionalität hinzufügen würde. Dies würde es erforderlich machen, den größten Teil des direkten Zugriffs auf Größenfunktionen / Datenelemente usw. durch Aufrufe von oben zu ersetzen, was das Lesen und damit die Wartung erleichtern würde.
Wie im vorherigen Poster vorgeschlagen, würde das Hinzufügen von isValid- oder canMultiply-Funktionen dazu beitragen, die Lösung robuster zu machen.