IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Optimisation des matrices


Sujet :

C++

  1. #1
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    182
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2007
    Messages : 182
    Par défaut Optimisation des matrices
    Bonjour à toutes et à tous,

    Je dois déporter un programme Matlab en C++ pour des questions de vitesse (because boucles en matlab). Je suis assez nouveau en C++ et plutôt que de partir d'un type int matrice [n][n] ou int** matrice, j'ai vu qu'il existe des librairies spécialement adaptées pour ce type de questions (traitement de matrices).

    Ma question est la suivante:
    Je dois faire des traitements très simples: initialiser des matrices de petites ou grandes tailles, modifier un grand nombre de valeurs dans une ou plusieurs matrices à chaque pas de temps, rien de plus compliqué.
    Du coup je me demande si les packages spécialement adaptés pour traiter les matrices ne seraient pas un peu surdimensionnés pour ce que je veux faire. Ils sont certainement adaptés pour des calculs plus compliqués (inversions, triangulations, etc.) mais dans mon cas, pour les affectations par exemple, est-ce que j'y gagnerais forcément en temps de calcul ?

    Je pose cette question car je suis sur un contrainte temps assez importante (pas du temps réel, mais je risque de me retrouver avec des matrices imposantes en milliers de lignes/colonnes).

    Merci par avance pour vos conseils.

    Gian

  2. #2
    Membre émérite
    Avatar de Ekleog
    Homme Profil pro
    Étudiant
    Inscrit en
    Janvier 2012
    Messages
    448
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2012
    Messages : 448
    Par défaut
    Utilises-tu les opérations mathématiques (addition, multiplication, ...) sur tes "matrices" ?

    Si oui, alors une librairie de matrices (p.ex. boost.ublas) serait intéressante.
    Si non, alors il est strictement inutile de passer par un paquet externe, et il suffit d'avoir un tableau à deux dimensions.

  3. #3
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    182
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2007
    Messages : 182
    Par défaut
    Eh bien, pour donner un ordre d'idée, en terme de temps, je n'effectue des opérations (additions, soustractions, etc.) entre deux ou plusieurs matrices que "rarement" (environ 5 à 10% du temps de calcul).
    Les 90 à 95% du temps restant est plutôt consacré à mettre à jour un grand nombre de valeurs des matrices par des opérations impliquant des scalaires, voire des vecteurs (plus rare). Pour donner un exemple:
    g(i,j) = c(i,j) + d(i,j)
    ou g, c et d sont des matrices et i,j les indices.
    J'ai aussi une composante temps qui consiste aussi à sauvegarder l'état des matrices entre chaque pas de temps (gourmand avec de grandes matrices donc).

  4. #4
    Membre émérite
    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mars 2009
    Messages
    552
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mars 2009
    Messages : 552
    Par défaut
    Tu as déjà optimisé dans matlab?

    Ca fait un bail que j'en ai pas fais, mais je pense que passer par des choses du style:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    for j=1:n,
        A(j,:) = A(j,:) - A(j-1,:)
    Au lieu de ,

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    for j=1:n,
        for i=1:m
               A(j,i) = A(j,i) - A(j-1,i)
    lui permet de dérouler le traitement en C voir même de paralléliser si c'est bien fait?

  5. #5
    Membre émérite
    Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Mars 2009
    Messages
    552
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Mars 2009
    Messages : 552
    Par défaut
    Pardon, mal lu, oublie mon poste

  6. #6
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    182
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2007
    Messages : 182
    Par défaut
    Pas de soucis!
    Sinon pour répondre à ta question, j'ai la pratique du Matlab, je sais qu'il faut tout écrire en matriciel et éviter les boucles, donc j'ai fait au mieux, mais il y a certaines boucles que je ne peux pas éviter.

    Merci quand meme

    Edit: Si ca peut aider, j'ai pas mal de min et max à calculer sur les matrices que j'ai et sur des parties plus "locales" des matrices (subset des matrices).
    Edit2: quand je parle de subset, j'ai beaucoup d'extraction de voisinages à faire (voisinage de Moore, etc.).

  7. #7
    Membre régulier
    Profil pro
    Inscrit en
    Mars 2012
    Messages
    9
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2012
    Messages : 9
    Par défaut
    hello,
    Pour la performance ce que tu dois faire, le minimum vital;
    - Definir une classe matrice basée sur un conteneur contigue
    - Pour toutes les opérations d'algèbre utiliser la lib blas (libre à toi
    de choisir la provenance, MKL intel, ACML amd, GOTO uni du texas)
    ou bien utiliser boost/blas

    example de base le plus simple possible produit de matrice de double (dgemm):

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
        typename T::value_type*ad;
        typename T::value_type*bd;
        typename T::value_type*cd;
     
        int m,n,k;
        int lda,ldb,ldc;
        double alpha(1.0), beta(1.0);
     
        m =(int) T::ValueX;
        n =(int) T::ValueY;
        k =(int) T::ValueY;
     
        lda = ldb = ldc = T::ValueX;
     
        ad = new typename T::value_type[T::ValueX*T::ValueY]; 
        bd = new typename T::value_type[T::ValueX*T::ValueY]; 
        cd = new typename T::value_type[T::ValueX*T::ValueY]; 
     
        memset((void*)cd,0,T::ValueX*T::ValueY*sizeof(typename T::value_type));
     
        for(int i(0); i< T::ValueX*T::ValueY ; ++i){
            ad[i] = Rd();
            bd[i] = Rd();
        }   
     
        TimerPTH t1("blas");
        t1.begin();
        dgemm("N","N", &m, &n, &k, &alpha, ad, &lda, bd, &ldb, &beta, cd, &ldc);
        t1.end();
     
        delete [] ad;   
        delete [] bd;   
        delete [] cd;   
    }

  8. #8
    Membre régulier
    Homme Profil pro
    Étudiant
    Inscrit en
    Février 2012
    Messages
    10
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Haut Rhin (Alsace)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Février 2012
    Messages : 10
    Par défaut
    bonsoirs,
    moi j'explore la librairie VXL qui contient la bibliothèque VNL du calcule numérique, te c'est je dirai mieux que MATLAB en traitement (relativement) des matrices. C'est très intéressant.

    ta aussi la bibliothèque armadillo qui a priori prêtent être mieux que Matlab mais que je n'ai pas encore tester.

    bonne courage

  9. #9
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    182
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2007
    Messages : 182
    Par défaut
    Merci pour ces retours,
    Je regarde avec détails ces packages.

    Gian

  10. #10
    Membre éclairé

    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Février 2005
    Messages
    464
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : France, Loire (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : Industrie

    Informations forums :
    Inscription : Février 2005
    Messages : 464
    Par défaut
    Dommage, Matlab est quand même fait pour ça ... peux-t-on vraiment espérer faire mieux ?


    Je t'invite à consulter le paragraphe Alternatives - si tu ne l'as pas déjà fait - de la page Wikipedia de Matlab on te cite quelques bibliothèques qui peuvent s'interfacer en C/C++

    Si tes matrices sont grandes, que tes traitements sont indépendants et que tu exécutes ton calcul sur du multi-coeur, tu peux envisager de paralléliser tes calculs avec des threads (peux-être cela se fait-il aussi sous Matlab ?).

  11. #11
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    182
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2007
    Messages : 182
    Par défaut
    On peut espérer faire mieux si un prog Matlab contient un grand nombre de boucles imbriquées non réductibles à du traitement matriciel (ce qui est mon cas).
    Mais une seule facon d'être sur, implémenter le code!

  12. #12
    Rédacteur/Modérateur
    Avatar de JolyLoic
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    5 463
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2004
    Messages : 5 463
    Par défaut
    Quelques questions supplémentaires : Tes matrices ont-elles une structure particulière (creuses ? Triangulaires ? Diagonales ? Autre ?). Est-ce que les travaux sur les différentes données sont assez indépendants les uns des autres, ou bien est-ce que tout agit sur tout se croisant dans tous les sens (si tu as un pipeline, peut-être une bonne solution est de regarder du côté de ton GPU, mais je ne maîtrise pas ce domaine).

    De ce que tu dis de ton problème (éléments entiers, voisinage...), je vois plus quelque-chose du côté traitement d'image que du côté matriciel au sens mathématique du terme. Si je me trompe, eigen est une bibliothèque de matrice dont j'ai entendu parler.

    En tout cas, je pense que quasiment tout sera préférable à une solution à base de matrice [n][n] ou int** matrice
    Ma session aux Microsoft TechDays 2013 : Développer en natif avec C++11.
    Celle des Microsoft TechDays 2014 : Bonnes pratiques pour apprivoiser le C++11 avec Visual C++
    Et celle des Microsoft TechDays 2015 : Visual C++ 2015 : voyage à la découverte d'un nouveau monde
    Je donne des formations au C++ en entreprise, n'hésitez pas à me contacter.

  13. #13
    Membre confirmé
    Profil pro
    Inscrit en
    Février 2007
    Messages
    182
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2007
    Messages : 182
    Par défaut
    Eh bien merci pour ces retours!
    Mes matrices sont communes (matrices carrées de réels), peut-être l'une d'entre elle est creuse, mais les autres non.
    Les travaux sur les données sont assez indépendant les uns des autres.

    Pour l'instant mon choix se porte sur Armadillo, en espérant que ce soit assez facile à utiliser... (je suis novice en C++). :]

Discussions similaires

  1. Réponses: 1
    Dernier message: 25/02/2012, 15h45
  2. optimisation des requêtes
    Par yech dans le forum PostgreSQL
    Réponses: 1
    Dernier message: 21/09/2004, 19h03
  3. [Compilateur] Optimisation des conditions
    Par Pedro dans le forum Langage
    Réponses: 2
    Dernier message: 16/06/2004, 13h49
  4. Optimisation des requetes
    Par bifidus dans le forum MS SQL Server
    Réponses: 5
    Dernier message: 06/10/2003, 11h29
  5. Réponses: 6
    Dernier message: 13/09/2003, 12h42

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo