Discussion :

[Rodrigue]

Bonjour,

Quelle est la meilleure méthode à adopter pour coder des matrices?
Je m'explique, je pourrais me contenter d'un:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

double* a = new double[n][n];

mais cela n'est pas "secure". Je souhaiterais utiliser la STL pour éviter les fuites mémoires.
Je pensais à

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

std::vector <std::vector <double> >

mais ce n'est pas très pratique pour les resizes (à faire sur chaque ligne...)

Si je pouvais déclarer mes matrices comme cela:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

matrix<double> m(3,3)

Ce serait génial.

Note importante: je n'ai pas besoin des opérations de base car il s'agit plus d'un conteneur qu'autre chose...

Auriez-vous une idée et/ou des conseils?

Cordialement,
Rodrigue

[Matthieu Brucher]

Effectivement, ce n'est pas le mieux, de plus l'espace mémoire n'est pas contigu.
Soit tu prends une bibliothèque existante à la boost::uBLAS, MTL, Blitz++, ... soit tu te fais une classe perso avec une surcharge de l'opérateur () qui prend 2 unsigned int et te renvoie le bon élément.

[Swoög]

Salut !

perso, pour les matrices, j'utilise généralement des map< pair<unsigned, unsigned>, T>
(où T est le type des éléments de la matrice)
C'est pas forcément le plus clean... mais en tous cas, c'est la version qui me parait la plus tranquile d'utilisation

[Rodrigue]

Swöög: je ne sais pas si c'est très performant d'utiliser des map ?

Miles: c'est vrai que je pourrais développer une telle classe... je vais essayer!

[Swoög]

Swoög: je ne sais pas si c'est très performant d'utiliser des map ?

bah, ça fait de la STL quand même...

et puis l'avantage, c'est que seuls les cases utilisées de la matrices sont allouées

[Matthieu Brucher]

Salut !

perso, pour les matrices, j'utilise généralement des map< pair<unsigned, unsigned>, T>
(où T est le type des éléments de la matrice)
C'est pas forcément le plus clean... mais en tous cas, c'est la version qui me parait la plus tranquile d'utilisation

C'est bien, mais pour des matrices creuses

[Rodrigue]

Bonjour,

C'est fait! Une classe template Matrix basée sur une autre classe template Row. J'ai surchargé les opérateurs [] pour ces deux classes.
Je sais créer une matrice comme ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Matrix<double> m(3,3);

et accéder aux éléments très facilement:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

m[2][1] = "3.13"

Cordialement,
Rodrigue

[loufoque]

J'ai surchargé les opérateurs [] pour ces deux classes.

Déconseillé.

http://www.parashift.com/c++-faq-lit...html#faq-13.11

[Rodrigue]

Je ne suis pas totalement convaincu
Car dans le type d'implémentation (,), à chaque accès à un élément on a une multiplication ... Tandis que dans le type d'implémentation [][], on renvoie un pointeur sur la ligne et ensuite on lit la case dans cette ligne...

Alors je comprends que si on doit lire la matrice en fonction des colonnes, on obtienne des performances médiocres (à chaque fois, il faut renvoyer le pointeur sur la ligne suivante). Je pense que c'est au programmeur à le savoir et à s'arranger pour que son algorithme lise ligne par ligne la matrice ... de cette manière, on renvoie un pointeur sur la ligne et on la parcoure etc.
OU implémenter sa matrice en fonction des colonnes (si son algo est prévu pour...).

Le mieux (et je vais y réfléchir) serait d'avoir une classe de matrice qui permettrait d'obtenir des pointeurs sur les lignes et sur les colonnes ... A mon avis, cela demanderait une duplication des données ... ou alors faire une sorte de tableau de colonne dont les éléments sont des pointeurs sur les cases des lignes (on calcule les multiplications une seule fois)... ça ferait deux pointeurs par éléments.

Hum

Cordialement,
Rodrigue

[Fiquet]

La même remarque en français dans notre FAQ

http://c.developpez.com/faq/cpp/?pag...E_matrix_array

Avec un exemple à la question/réponse juste au-dessus.

[Matthieu Brucher]

Déconseillé.

http://www.parashift.com/c++-faq-lit...html#faq-13.11

C'est normal, mais si pour lui, le goulot d'étranglement n'est pas là, on s'en fout.

[Charlemagne]

Car dans le type d'implémentation (,), à chaque accès à un élément on a une multiplication ... Tandis que dans le type d'implémentation [][], on renvoie un pointeur sur la ligne et ensuite on lit la case dans cette ligne...

Mauvaise déduction.
p[n*i+j] est plus rapide que p[i][j] car
- les processeurs (type Intel) ont des instructions spéciales pour coder p[n*i+j]
- p[i][j] fait 2 accès mémoire (operation lente), alors que p[n*i+j] n'en fait qu'un seul
- faire un vecteur de vecteurs est très constraignant pour l'allocation et la désallocation

Si maintenant tu veux encore oprimiser l'accès sur une ligne il faut précalculer le décalage, et faire quelque chose du genre

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
 
class MatrixRow
{
  ...
  MatrixRow(Matrix &X, int i) : p(&X(i,0)) {}
 
  value_type       &operator[](int i)       { return p[i]; }
  const value_type &operator[](int i) const { return p[i]; }
};
 
class Matrix
{
  ...
 
  MatrixRow row(int i) { return MatrixRow(*this,i); }
 
  value_type       &operator()(int i,int j)       { return p[n*i+j]; }
  const value_type &operator()(int i,int j) const { return p[n*i+j]; }
};

[Rodrigue]

Ok, ok, je me rends ... !

Mauvaise déduction.
p[n*i+j] est plus rapide que p[i][j] car
- les processeurs (type Intel) ont des instructions spéciales pour coder p[n*i+j]
- p[i][j] fait 2 accès mémoire (operation lente), alors que p[n*i+j] n'en fait qu'un seul
- faire un vecteur de vecteurs est très constraignant pour l'allocation et la désallocation

J'ai appris quelque chose ... Merci!

Donc en résumé, il vaut mieux que je prenne pour mes matrices l'implémentation qui est donnée dans la FAQ: http://c.developpez.com/faq/cpp/?pag...E_matrix_index

L'implémentation est 2x plus facile que ma classe actuelle (ça me dégoûte ...)

Merci à tous pour vos réponses très instructives!

[Charlemagne]

Encore une précision.
Un vecteur de pointeurs peut quand-même être une solution intéressante dans le cas (peu probable) où ton programme échangerait très souvent la place des lignes. Une fonction membre swap n'aurait alors qu'à permuter les pointeurs.
Et alors l'encapsulation rend tout le mécanisme interne transparent pour l'utilisateur.

[loufoque]

permuter des pointeurs ou permuter des doubles c'est kif-kif.
Et utiliser des pointeurs aménerait tout un tas d'autres problèmes. (en plus le vector alloue intelligemment tout en même temps, si tu passes par des new ça va être plus lent)

[Tipoun]

Utiliser des pointeurs prend de la place ! Une adresse prend 8 octets de mémoire

[Charlemagne]

Il suffirait de permuter 2 pointeurs pour permuter toute une ligne.
Donc c'est pas kif-kif.
J'ai bien dit que cette technique ne serait rentable que rarement.
Et j'ai bien conseillé dans le cas général de ne pas utiliser cette structure de données.

Je crois plutôt que sur une machine 32 bits:
-sizeof(void*)=4
-sizeof(double)=8

[Tipoun]

Je crois plutôt que sur une machine 32 bits:
-sizeof(void*)=4
-sizeof(double)=8

Cela dépend de la machine, du systéme d'exploitation...

La norme ne préconise aucune valeur fixe

[Charlemagne]

Cela dépend de la machine, du systéme d'exploitation...

C'est bien pour ça que j'ai précisé sur une machine 32 bits.
De toute façon là n'est pas le problème car:
-1 pointeur = 1 registre
-échanger 2 pointeurs sera toujours plus rapides que de permuter le contenu de 2 vecteurs
-le volume mémoire occupés par les pointeurs sera négligeable comparé aux données, car il n'y aurait qu'un seul pointeur par ligne de la matrice
-et pourquoi se contenter de doubles? ça pourrait être une matrice de grosses structures

[Laurent Gomila]

-échanger 2 pointeurs sera toujours plus rapides que de permuter le contenu de 2 vecteurs

std::vector::swap ne fait que permuter les pointeurs, il ne s'amuse pas à copier les données. Bon il y a également permutation des tailles, mais on peut considérer ça comme négligeable...