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 :

transposer un vecteur de vecteur sans boucle for


Sujet :

C++

  1. #1
    Membre du Club
    Femme Profil pro
    Développeur informatique
    Inscrit en
    Juillet 2009
    Messages
    171
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Juillet 2009
    Messages : 171
    Points : 62
    Points
    62
    Par défaut transposer un vecteur de vecteur sans boucle for
    Bonjour,
    J'ai un petit problème que je n'arrive pas à résoudre !
    Je dispose en entrée de la variable suivante :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    std::vector<std::vector<double>> tableau;
    il est de taille C * L
    C'est à dire qu'il comporte "C" tableaux contenant chacun "L" valeurs numériques (double);
    On peut se le représenter comme une "matrice" contenant "C" colonnes et "L" lignes.

    J'aimerai pouvoir "transposer" cette matrice. C'est à dire obtenir un tableau de taille L*C.

    Le but de cette transformation est de pouvoir calculer le min et max de chaque "ligne" de la matrice initiale à l'aide d'un calcul utilisant un std;;valarray.

    Je souhaite effectuer cette transformation sans boucle for à cause de la dimension L qui peut atteindre une taille de 200000 valeurs

    J'espère que j'ai été claire ! Est ce que qqn aurait une piste à me proposer ?
    Merci

  2. #2
    Membre expérimenté
    Homme Profil pro
    Inscrit en
    Décembre 2010
    Messages
    734
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Décembre 2010
    Messages : 734
    Points : 1 475
    Points
    1 475
    Par défaut
    En somme tu souhaites traiter toutes les valeurs...sans traiter toutes les valeurs?

  3. #3
    Expert éminent sénior
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Février 2005
    Messages
    5 074
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Conseil

    Informations forums :
    Inscription : Février 2005
    Messages : 5 074
    Points : 12 120
    Points
    12 120
    Par défaut
    Si L est constante pour un tableau donné, utiliser un vector<vector<T>> est une erreur.
    Si C est une constante à la compilation, utiliser un vector<T> est une erreur.

    Si L et C sont des variables et que la densité de données est faible, il existe des classes de type matrices "creuses" dans plusieurs bibliothèques mathématiques.

  4. #4
    Membre du Club
    Femme Profil pro
    Développeur informatique
    Inscrit en
    Juillet 2009
    Messages
    171
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Juillet 2009
    Messages : 171
    Points : 62
    Points
    62
    Par défaut
    Merci pour ta réponse.

    L et C ne sont pas des constantes mais varient à chaque appel de la fonction donc je suis obligée de passer par des std::vector.
    Je vais regarder du coté des matrices "creuses" alors!

  5. #5
    Membre expérimenté
    Homme Profil pro
    Inscrit en
    Décembre 2010
    Messages
    734
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Décembre 2010
    Messages : 734
    Points : 1 475
    Points
    1 475
    Par défaut
    Plus sérieusement, la matrice transposée resservira t'elle, ou non? Si c'est seulement pour faire ces calculs de max, il vaut peut-être mieux se contenter de faire la comparaison au fil du parcours de la matrice...

  6. #6
    Membre du Club
    Femme Profil pro
    Développeur informatique
    Inscrit en
    Juillet 2009
    Messages
    171
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Juillet 2009
    Messages : 171
    Points : 62
    Points
    62
    Par défaut
    Non la matrice ne me resservira pas par la suite une fois les calculs de min et max seront effectués.

    Le code implémenté actuellement consiste en une boucle for avec itération sur les lignes de mon tableau et calcul au fur et à mesure des min et max..
    Mais le problème que j'ai est que le nombre de lignes est souvent très important et le parcours de la boucle est particulièrement long. C'est pour ça que je voulais savoir s'il existait un moyen d'implémenter ce code sans boucle for

  7. #7
    Membre expérimenté
    Homme Profil pro
    Inscrit en
    Décembre 2010
    Messages
    734
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Décembre 2010
    Messages : 734
    Points : 1 475
    Points
    1 475
    Par défaut
    La piste des matrices creuses revient à retravailler la représentation initiale de la matrice. Peux tu remplacer ce vector de vector par autre chose? La notion de matrice creuse revient à dire: "j'ai une matrice L*C car ce sont les dimensions de mon espace, mais la pluspart des valeurs sont nulles" et employer des optimisations pour ne pas traiter les valeurs nulles.
    Autre possibilité: le parcours se fait aussi au remplissage, peut-être peux-tu en profiter pour calculer le min et le max. Si les valeurs rechangent par la suite, tu peux (par exemple en encapsulant tes données dans une classe qui fait ce contrôle) maintenir ces min/max à jour en traitant simplement l'ancienne et la nouvelle valeur de la donnée mise à jour.

  8. #8
    Membre expert
    Profil pro
    Inscrit en
    Mars 2007
    Messages
    1 415
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Mars 2007
    Messages : 1 415
    Points : 3 156
    Points
    3 156
    Par défaut
    Salut

    Je soutiens les propositions de therwald.

    Si les matrices creuses ne peuvent pas être utilisées pour ton problème, un vector de vector reste une mauvaise idée. Il vaut mieux utiliser un seul vector de taille C*L et accéder aux éléments en calculant leur indice. Par exemple, l'élément situé à la 3ème colonne et à la 4ème ligne peut se situer à l'index C*3 + 4. La FAQ contient des exemples à ce sujet. Pour avoir une matrice transposée, il n'y a rien à faire à part calculer l'index différemment.

    Construire une matrice transposée pour ensuite la parcourir afin de calculer des min et max a peu de sens. Le faire, pour ensuite construire des valarray pour ensuite les parcourir (même si c'est caché dans la fonction membre max) est encore pire. Allouer et copier de la mémoire est coûteux. Tu ne gagneras pas en performances en faisant ceci, et tu n'éviteras pas le parcours.
    Find me on github

  9. #9
    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 : 49
    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
    Points : 16 213
    Points
    16 213
    Par défaut
    Qu'est-ce que tu appelles long ? Je serais curieux de voir s'il n'y a pas déjà des problèmes dans la solution telle qu'elle existe.
    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.

  10. #10
    Membre du Club
    Femme Profil pro
    Développeur informatique
    Inscrit en
    Juillet 2009
    Messages
    171
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Isère (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Juillet 2009
    Messages : 171
    Points : 62
    Points
    62
    Par défaut
    Merci à tous pour vos suggestions. Je vais les étudier avec attention.
    Pour info voila une partie du code en question tel qu'il était jusqu'à présent :

    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
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
     
     
      typedef std::pair<double,double>    PointDuGraphe;
      typedef std::vector<PointDuGraphe>  Spectre;
      typedef std::vector<PointDuGraphe>  Graphe;
     
    void GestionnaireNonThread::calculDeltaMax( Graphe & outGrapheDeltaMax, double & outDeltaDSRF )
          {
            // récupérer le tableau de spectres
            QSharedPointer<std::vector<Spectre>> tempSpectre = QSharedPointer<std::vector<Spectre>>( new std::vector<Spectre>() );
            tempSpectre = _donnees.getTableauDesSpectres();
            // récupérer le nombre de spectres
            int nbSpectres = tempSpectre->size();
            // vérifier qu'il y a bien + qu'un seul spectre
            if( nbSpectres > 0 )
            {
              // vérifier que tous les spectres ont la même dimension en X
              // récupération de la taille du premier spectre
              int tempTaille = tempSpectre->at(0).size();
              for( int i=1; i < nbSpectres ;++i )
              {
                if( tempSpectre->at(i).size() != tempTaille )
                  throw MessageManagement::Error( MSG_CODE_LOCATION(), "Impossible de calculer le delta max des graphes car ils n'ont pas la même dimension en X." );
              }
              // On redimensionne la variable  outGrapheDeltaMax
              outGrapheDeltaMax.resize( tempTaille );
              // calculer le delta max
              double valAmplitudeMin = 0., valAmplitudeMax = 0.;
              std::vector<double> tempValeurAmplitudePourUneLongueurDOnde;
              tempValeurAmplitudePourUneLongueurDOnde.resize( nbSpectres, 0. );
              for( int iLongueurDOnde = 0; iLongueurDOnde< tempTaille; ++iLongueurDOnde )
              {
                // boucle sur chaque longueur d'onde
                // on remplit la partie X de la variable outGrapheDeltaMax
                outGrapheDeltaMax.at( iLongueurDOnde ).first = tempSpectre->at(0).at( iLongueurDOnde ).first;
                // on crée un tableau avec toutes les valeurs d'amplitude pour une longueur d'onde donnée
                for( int iSpectre = 0; iSpectre < nbSpectres; ++ iSpectre )
                  tempValeurAmplitudePourUneLongueurDOnde.at(iSpectre) = tempSpectre->at(iSpectre).at( iLongueurDOnde ).second;
                // calcul du min et du max du tableau
                FonctionsGeneriques::calculMinMaxTabDouble( tempValeurAmplitudePourUneLongueurDOnde, valAmplitudeMin, valAmplitudeMax );
                // calcul du delta
                outGrapheDeltaMax.at( iLongueurDOnde ).second = abs( valAmplitudeMax - valAmplitudeMin );
                // sauvegarde dans les données
                _donnees.setDeltaMaxFonctionLongueurDOnde( outGrapheDeltaMax) ;
                _donnees.setDeltaDsrf( outDeltaDSRF );
              }
            }
          }
     
          bool FonctionsGeneriques::calculMinMaxTabDouble( const std::vector<double> & inTableau, double & outMin, double & outMax )
    {
      bool res = true;
      size_t nbPoint = inTableau.size();
      if( nbPoint != 0 )
      {
        outMin = inTableau.at(0);
        outMax = inTableau.at(0);
        for( unsigned int i=0; i<nbPoint; ++i )
        {
          double tempValue = inTableau.at(i);
          if( tempValue < outMin )
            outMin = tempValue;
          else if( tempValue > outMax )
            outMax = tempValue;
        }
      }
      else
      {
        res = false;
        outMin = 0., outMax = 0.;
        throw MSG_CATCH( "On ne peut pas calculer le min et le max du tableau car sa taille est nulle" );
      }
      return res;
    }

  11. #11
    Membre expérimenté
    Homme Profil pro
    Inscrit en
    Décembre 2010
    Messages
    734
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Décembre 2010
    Messages : 734
    Points : 1 475
    Points
    1 475
    Par défaut
    Première chose: pourquoi itérer une première fois entièrement pour contrôler les tailles des lignes, puis recommencer à itérer pour faire les calculs? Tu peux déjà gagner en faisant ce contrôle au fil de l'eau, quitte à commencer le calcul puis partir en erreur dès que tu constates une différence de taille.
    Par ailleurs, une fois que tu as la taille des lignes, tu devrais plutôt utiliser [] plutôt que at() car at() revérifie la taille et donc tu perds du temps.
    Sauf erreur, en itérant d'abord sur l'indice au sien des tableaux (longueur d'onde) dans ta boucle extérieure pour passer dans tous tes tableaux dans la boucle intérieur, tu te places dans le pire cas au niveau cache.
    Il serait plus judicieux à mon sens de procéder ainsi:
    =>au lieu de ta table d'amplitude, tu crées une table de min, une table de max
    =>tu itères (boucle extérieure) sur tes spectres
    =>en début d'itération, tu places ton contrôle d'égalité sur les tailles
    =>pour chaque spectre, tu itères sur les fréquences (boucle intérieure) pour mettre à jour tes tables de min et de max
    ainsi tu profites des optimisations d'accès mémoire du cache
    Concernant le calcul des amplitudes, je dirais qu'il vaut mieux itérer sur tes min et max pour les calculer après la fin de l'itération sur les spectres.

    Après, comme tes spectres sont effectivement encapsulés dans des objets, et doivent forcément être peuplés à un moment donné, je te suggère de calculer / mettre à jour tes min et max quand tu les peuples, sauf si tu mets à jour ta courbe de delta max BEAUCOUP, mais alors BEAUCOUP moins souvent que tes spectres individuels...

  12. #12
    Expert éminent sénior

    Avatar de dragonjoker59
    Homme Profil pro
    Software Developer
    Inscrit en
    Juin 2005
    Messages
    2 031
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Bas Rhin (Alsace)

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

    Informations forums :
    Inscription : Juin 2005
    Messages : 2 031
    Points : 11 474
    Points
    11 474
    Billets dans le blog
    11
    Par défaut
    L'initialisation faite dans cette ligne QSharedPointer<std::vector<Spectre>> tempSpectre = QSharedPointer<std::vector<Spectre>>( new std::vector<Spectre>() ); est inutile car tu réaffectes juste après tempSpectre : tempSpectre = _donnees.getTableauDesSpectres();.
    Par ailleurs, il me semble étrange de récupérer un pointeur sur un vector. Pourquoi pas une référence? Ca te permettrait de passer facilement à l'opérateur [] plutôt que d'utiliser at qui comme dit par therwald effectue une vérification de non dépassement à chaque fois...

    De plus, l'itération sur un vector devrait plutôt se faire via des iterator, au pire tu auras les mêmes performances, au mieux tu pourrais y gagner
    Si vous ne trouvez plus rien, cherchez autre chose...

    Vous trouverez ici des tutoriels OpenGL moderne.
    Mon moteur 3D: Castor 3D, presque utilisable (venez participer, il y a de la place)!
    Un projet qui ne sert à rien, mais qu'il est joli (des fois) : ProceduralGenerator (Génération procédurale d'images, et post-processing).

Discussions similaires

  1. "Comparer" un vecteur à une matrice sans boucle for
    Par nawellee dans le forum MATLAB
    Réponses: 2
    Dernier message: 27/04/2013, 20h55
  2. fonction colon pour cell (sans boucle for)
    Par soft001 dans le forum MATLAB
    Réponses: 1
    Dernier message: 11/09/2011, 13h11
  3. [Dojo] Recherche d'un attribut dans iframe sans boucle for
    Par Lionkid dans le forum Bibliothèques & Frameworks
    Réponses: 1
    Dernier message: 21/10/2010, 14h58
  4. Remplir la diagonale d'une matrice sans boucle FOR-END
    Par francois_S dans le forum MATLAB
    Réponses: 3
    Dernier message: 30/03/2010, 08h32
  5. Comparaison de deux matrices sans boucle for
    Par zicos dans le forum MATLAB
    Réponses: 8
    Dernier message: 04/05/2007, 18h16

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