STL et les matrices...

Version imprimable

04/05/2006, 16h04
Rodrigue

STL et les matrices...

Bonjour,

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

Code:

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:

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:

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
04/05/2006, 16h12
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.
04/05/2006, 16h13
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 ;)
04/05/2006, 16h27
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!
04/05/2006, 16h31
Swoög

Citation:

Envoyé par Rodrigue

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 ;)
04/05/2006, 19h05
Matthieu Brucher

Citation:

Envoyé par 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 ;)

C'est bien, mais pour des matrices creuses ;)
05/05/2006, 12h18
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:

Matrix<double> m(3,3);

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

Code:

m[2][1] = "3.13"

Cordialement,
Rodrigue
05/05/2006, 13h43
loufoque

Citation:

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

Déconseillé.

http://www.parashift.com/c++-faq-lit...html#faq-13.11
05/05/2006, 14h32
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
05/05/2006, 14h54
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.
05/05/2006, 15h46
Matthieu Brucher

Citation:

Envoyé par loufoque

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.

Citation:

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:

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

05/05/2006, 19h48
Rodrigue

Ok, ok, je me rends ... :aie: !

Citation:

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 :hola:... 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 :oops: ...)

Merci à tous pour vos réponses très instructives!
05/05/2006, 20h33
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.
06/05/2006, 13h19
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)
06/05/2006, 13h31
Tipoun

Utiliser des pointeurs prend de la place ! Une adresse prend 8 octets de mémoire 8O
06/05/2006, 13h34
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
06/05/2006, 14h05
Tipoun

Citation:

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 :?
06/05/2006, 14h49
Charlemagne

Citation:

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
06/05/2006, 16h05
Laurent Gomila

Citation:

-é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...

Il faut vraiment mettre les points sur les i dans cette discussion.

Je ne parle pas d'un vecteur de vecteurs STL, mais de vecteurs de pointeurs comme en C, du style float **p.
Je ne parle pas de de la fonction std::swap mais d'une fonction membre swap de la classe matrix.
Je parlais d'échanger le contenu de 2 lignes.
Si la STL devait intégrer dans l'avenir une classe matrix, je doute franchement qu'elle se base sur les std::vector.
Et encore une fois ce n'est pas la structure de données que je préconise dans le cas général.
cf. MTL (librairie qui n'est plus maintenue depuis pas mal d'années)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 template<class T,class Alloc> class matrix { ... size_t m,n; value_type **p; matrix(size_t h, size_t l) : m(h), n(l) { p=...} ~matrix() {...} void swap_row(size_t i0, size_t i1) { std::swap(p[i0],p[i1]); } void swap_col(size_t j0, size_t j1) { for (int i=0; i<m; ++i) ...} value_type &operator()(size_t i, size_t j) { return p[i][j]; } const value_type &operator()(size_t i, size_t j) const { return p[i][j]; } ... };

08/05/2006, 20h22
Rodrigue

Merci à tous!

J'ai suivi vos conseils, j'ai recodé ma matrice pour qu'elle utilise les opérateurs () à la place [][]. Le code est plus lisible :)