Optimisation de l'algorithme de multiplication matricielle

Dec 28 2020

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 Vds qu'elle contient.

Je suis particulièrement intéressé par la fonction matrixDotdans 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

1 Edward Dec 30 2020 at 04:55

Je vois certaines choses que vous pourriez souhaiter utiliser pour améliorer votre code.

Utiliser le usingcas é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::endlsi vous n'en avez pas vraiment besoin

La différence entre std::endlet '\n'est qu'émet '\n'simplement un caractère de nouvelle ligne, tout std::endlen 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::endllorsque 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::endlquand '\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::copyet 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 matrixDotrenvoyer 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 Mdet Vdsont mis en œuvre comme structavec 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 classet d'utiliser un seul vectorpour 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_listarguments, je suggérerais également certains des autres opérateurs tels que operator==pour cette classe.

3 Bhaskar Dec 28 2020 at 09:20

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 matrixDotfonction 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::arrayplutôt std::vectorque la mesure où vous êtes conscient de la longueur des lignes et des colonnes au moment de la création.

3 GarryR Dec 29 2020 at 16:57

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.