Discussion :

[Invité]

Bonsoir à tous !

J'ai besoin d'aide, je suis en train de travailler sur un projet de matrices creuses de grandes tailles 200x200 notamment modifier une librairie existante pour l'optimisée. J'ai déjà effectué avec succès les opérations plus et inf pour des matrices représentées std::vector, mon problème est pour l'opération transpose, qui est très très lente par rapport à l'existant....

voici le début de la classe matrixvector

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
 
 
struct Ttriplet
{
 Ttriplet(int I, int J,serie S):i(I),j(J),s(S){}
int i;
int j;
serie s;
        int geti(){return this->i;}
        int getj(){return this->j;}
        void seti(int k){i=k;}
        void setj(int k){this->j=k;}
        serie gets(){return this->s;}
        void sets(serie sa){this->s=sa;}
} ;
 
class matrixvector{
private :
		 int col,row;
		 unsigned int size,capacity;
 
         std::vector<Ttriplet *> Data;
...

et le code de la fonction transpose:

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
 
matrixvector transpose(matrixvector& a)
 {
    matrixvector result;
    //result.Data.reserve(a.size);
    Ttriplet *temp;
    int n=0,i=0,j=0;
    n=a.getsize();
    result.row=a.getcol();
    result.col=a.getrow();
     result.size=0;
    if(n>0)
    {
        result.size=1;
        for(i=0;i<a.col;++i)
        {
            for(j=0;j<n;++j)
            {
              //  std::cout<<a.Data[j]->j<<std::endl;
               if((a.Data.at(j)->j==i))
                    {
                        temp=new Ttriplet(a.getj(j),a.geti(j),a.Data[j]->s);
                        result.Data.push_back(temp);
                        result.size++;
                    }
//
            }
 
        }
         return(result);
    }
 
      else
    {
        mem_limite  l(28);   throw(l);
    }
 
 }

test:


Merci !

[oodini]

Si tu te soucies des performances, commence par utiliser [] plutôt que at().

[Bousk]

Bonjour,

il est dommage d'avoir supprimer une des plus grandes sources d'optimisation de l'utilisation du std::vector : vector::reserve.
Ton vector se remplit à coup de push_back... ce qui entraîne désallocation et réallocation en chaîne.
L'utilisation de at est également à proscrire.

Après dans les plus petites optimisations possibles
- préfère la préincrémentation à la postincrémentation
- éviter d'utiliser des variables temporaires, même pour ne stocker qu'un vecteur, tu peux faire un push_back(new T)
- pourquoi stocker result.size et l'incrémenter à chaque push_back ? vector possède sa fonction size (en temps constant) ... qu'il suffit d'appeler à la fin
- passer la matrix resultat en paramètre out plutôt que par return, ça évite une copie

qu'est-ce que serie ? pourquoi ne pas le retourner en const& ?
pourquoi il n'est pas en const& dans le paramètre de sets ?

[gbdivers]

bonjour geoberto et bienvenue sur le forum

La programmation de libs numérique est un domaine complexe et à la vue de ton code, j'ai l'impression que tu débutes, non ?
Je te conseille de regarder les libs existantes et voir comment ce type de problématique est résolue, tu apprendras beaucoup comme ça
Par exemple (mais non exclusif) :
boost.uBlas http://www.boost.org/doc/libs/1_50_0.../doc/index.htm
nt2 http://nt2.lri.fr/contents.html

[Matthieu Brucher]

bonjour geoberto et bienvenue sur le forum

La programmation de libs numérique est un domaine complexe et à la vue de ton code, j'ai l'impression que tu débutes, non ?
Je te conseille de regarder les libs existantes et voir comment ce type de problématique est résolue, tu apprendras beaucoup comme ça
Par exemple (mais non exclusif) :
boost.uBlas http://www.boost.org/doc/libs/1_50_0.../doc/index.htm
nt2 http://nt2.lri.fr/contents.html

Et ma préférée : Eigen http://eigen.tuxfamily.org/

[Matthieu Brucher]

Il y a une petite différence de performance entre l'opérateur [], un iterateur et un pointeur nu (double p = &t[0]. Certain diront non (que ça dépend entre autre des options de compilation)

Ici, la différence entre vecteur et un tableau C-style est négligeable par rapport à tous les autres problèmes de conception, en particulier l'utilisation de push_back et l'absence de reserve. Il y a aussi le problème de new (faire 200*200 allocations ou presque, c'est pas top)

Bref, comme d'hab -> profiling avant de chercher à faire de la micro-optimisation sur vector, un appel de fonction ou un déréférencement de pointeur

On lit ca et on l’exécute, puis on arrête de dire des bêtises sur std::vector

Je réponds aux deux d'un coup. Sur Visual Studio, il me smeble que at() et [] font de la vérification. Pour at(), c'est obligatoire d'après la norme, mais pour [] ce n'est pas obligatoire de ne pas tester. Pour des raisons de sécurité, Microsoft a laissé le test.

[Invité]

Merci Bousk, mais c'est toujours aussi lent, la lenteur vient probablement du pushback...

Le reserve ne change rien quel que soit la taille.

Oui Guillaume je débute, j'ai déjà essayé avec un tableau de Ttriplet et j'ai passé une éternité à créer moi-même un pushback et à gérer les allocations dynamiques donc j'ai choisi d'utiliser les vector. Merci pour les libs je vais regarder ça.

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
 
void transpose(matrixCOOvector& a, matrixCOOvector &b)
 {
    //matrixCOOvector result;
    b.Data.reserve(a.size);
    Ttriplet *temp;
    int i=0,j=0;
    b.row=a.getcol();
    b.col=a.getrow();
    if(a.size>0)
    {
        for(i=0;i<a.col;++i)
        {
            for(j=0;j<a.size;++j)
            {
              //  std::cout<<a.Data[j]->j<<std::endl;
               if((a.Data[j]->j==i))
                    {
                     //  temp=new Ttriplet(a.getj(j),a.geti(j),a.Data[j]->s);
                        b.Data.push_back(new Ttriplet(a.getj(j),a.geti(j),a.Data[j]->s));
 
                    }
//
            }
 
        }
                b.size=b.Data.size();
    }
 
      else
    {
        mem_limite  l(28);   throw(l);
    }
 
 }

[JolyLoic]

Pourquoi utiliser des pointeurs et de l'allocation dynamique ?

[oodini]

Pour ce genre de problèmes, n'utilise pas des vecteurs, mais du stockage à l'ancienne à base de pointeurs. En plus de gagner en efficacité, tu pourras plus facilement extraire des colonnes.

Et quand tu peux, alloue la mémoire en une seule fois.

[Klaim]

Je vois pas pourquoi utiliser un vecteur avec les valeurs au lieu des pointeurs , réservé à la taille finale, serait moins bien que faire ce que tu viens de dire?

[ternel]

Parce que tu économiserais en pointeurs, appels de fonctions et autres?

[Joel F]

Pour ce genre de problèmes, n'utilise pas des vecteurs, mais du stockage à l'ancienne à base de pointeurs. En plus de gagner en efficacité, tu pourras plus facilement extraire des colonnes.

Et quand tu peux, alloue la mémoire en une seule fois.

On lit ca et on l’exécute, puis on arrête de dire des bêtises sur std::vector