Optimisation de l'algorithme de multiplication matricielle
J'ai implémenté ma propre version d'algorithme pour multiplier deux matrices ensemble et j'ai besoin de quelqu'un qui sait ce qu'il fait pour voir s'il y a quelque chose qui peut être fait de manière plus optimale. Je suis également désireux de comprendre comment je peux le rendre robuste de sorte qu'il ne plante pas lorsque des matrices non rectangulaires sont passées en argument, c'est-à-dire une matrice qui a un nombre impair d'éléments dans différents Vd
s qu'elle contient.
Je suis particulièrement intéressé par la fonction matrixDot
dans le code ci-dessous, tout le reste n'est que pour montrer comment je l'utilise dans mon projet).
#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;
}
Réponses
Je vois certaines choses que vous pourriez souhaiter utiliser pour améliorer votre code.
Utiliser le using
cas échéant
Le code contient actuellement ceci:
struct Vd
{
std::vector<double> v;
};
Ceci est probablement mieux exprimé comme ceci à la place:
using Vd = std::vector<double>;
Alors maintenant, au lieu d'écrire ceci:
out << mat.m[i].v[j] << ", ";
Nous pouvons utiliser cette syntaxe plus propre:
out << mat.m[i][j] << ", ";
Comprendre l'en-tête inclure les chemins
Il y a une différence subtile entre #include "iostream"
et #include <iostream>
. Bien que son implémentation soit définie, la plupart des implémentations du compilateur sont que le formulaire de guillemets recherche d'abord localement (par exemple le répertoire courant), puis recherche dans le système les répertoires inclus si cela échoue. La forme de crochet angulaire recherche généralement dans les répertoires d'inclusion système. Consultez cette question pour en savoir plus. Pour cette raison, ce code devrait probablement utiliser #include <iostream>
.
Ne l'utilisez pas std::endl
si vous n'en avez pas vraiment besoin
La différence entre std::endl
et '\n'
est qu'émet '\n'
simplement un caractère de nouvelle ligne, tout std::endl
en vidant le flux. Cela peut prendre du temps dans un programme avec beaucoup d'E / S et est rarement nécessaire. Il est préférable de ne l' utiliser que std::endl
lorsque vous avez une bonne raison de vider le flux et que ce n'est pas très souvent nécessaire pour des programmes simples tels que celui-ci. Éviter l’habitude d’utiliser std::endl
quand '\n'
fera sera payant à l’avenir, car vous écrivez des programmes plus complexes avec plus d’E / S et où les performances doivent être maximisées.
Utilisez les fonctions standard le cas échéant
Plutôt que d'écrire le ostream& operator<<
comme vous l'avez fait, une alternative intéressante serait d'utiliser std::copy
et std::experimental::ostream_joinercomme ceci:
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";
}
Préférez les valeurs de retour aux paramètres de sortie
Il semble beaucoup plus logique de matrixDot
renvoyer une nouvelle matrice, plutôt que d'utiliser le troisième paramètre comme paramètre de sortie. Voir F.20 pour plus de détails.
Envisagez une représentation alternative
Ce code est un peu fragile que les deux Md
et Vd
sont mis en œuvre comme struct
avec tous les publics membres. Pire encore, nous pourrions avoir un tableau irrégulier dans lequel chaque ligne n'a pas le même nombre d'éléments. Cela n'entraînera probablement rien de bien. Pour ces deux raisons, je suggère d'utiliser un class
et d'utiliser un seul vector
pour contenir tous les éléments. Consultez cette question pour obtenir des idées et des conseils sur la façon de procéder. Vous pouvez également considérer std::valarraycomme un type sous-jacent.
Fournir une implémentation de classe complète
En plus d'un constructeur prenant des std::initializer_list
arguments, je suggérerais également certains des autres opérateurs tels que operator==
pour cette classe.
Je dois admettre que je suis un peu confus, vous avez fait les parties difficiles et vous avez une question sur les parties faciles? Je ne comprends peut-être pas votre question.
Je suis également désireux de comprendre comment je peux le rendre robuste de sorte qu'il ne plante pas lorsque des matrices non rectangulaires sont passées en argument, c'est-à-dire une matrice qui a un nombre impair d'éléments dans différents Vds qu'elle contient.
Vous pouvez valider que vous avez une matrice bien formée en
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;
}
et l'incorporer dans la matrixDot
fonction de validation similaire à la validation de forme que vous avez actuellement
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();
}
Toutes les optimisations auxquelles je peux penser concernent l'utilisation std::array
plutôt std::vector
que la mesure où vous êtes conscient de la longueur des lignes et des colonnes au moment de la création.
Personnellement, j'étendrais la structure Md (classe) pour qu'elle encapsule complètement la matrice. Il aurait:
-> Variables membres pour:
The number of rows and columns.
Vector to hold the data. (Consider one dimensional array here).
-> Constructeur qui permettrait de créer une matrice de bonne taille (lignes, cols).
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.
-> Obtenir des fonctions pour obtenir le nombre de lignes / colonnes
-> Fonctions Get / Set pour obtenir / définir les valeurs des données de la matrice.
Get/Set functions implement bounds checking.
Je dériverais alors une classe mathMatrix qui ajouterait la fonctionnalité de multiplication de matrice. Cela nécessiterait de remplacer la plupart de l'accès direct aux fonctions de taille / éléments de données, etc. par des appels provenant de ce qui précède, ce qui faciliterait la lecture et donc la maintenance.
Ensuite, comme l'a suggéré l'affiche précédente, l'ajout des fonctions isValid ou canMultiply aiderait à rendre la solution plus robuste.