transposer un vecteur de vecteur sans boucle for

Version imprimable

14/10/2014, 16h25
cedji

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:

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 :)
14/10/2014, 16h39
therwald

En somme tu souhaites traiter toutes les valeurs...sans traiter toutes les valeurs?
14/10/2014, 16h42
bacelar

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.
14/10/2014, 16h50
cedji

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!
14/10/2014, 16h57
therwald

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...
14/10/2014, 17h07
cedji

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
14/10/2014, 17h17
therwald

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.
14/10/2014, 17h59
jblecanard

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.
14/10/2014, 18h17
JolyLoic

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.

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:

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;
}

15/10/2014, 11h02
therwald

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...
24/10/2014, 14h45
dragonjoker59

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