[Langage] Classe Matrice et opérations

Bonjour,

J'ai l'intention de me créer un type de données, soit les matrices creuses.
Je ne veux que stocker les éléments différents de zéro.

Dans le choix de la représentation, il faut tenir compte que je vise ensuite la possibilité de faire les opérations de base sur différentes matrices.
Exemple, l'addition de m1 + m2, la soustraction, la multiplication par un scalaire et la multiplication.

Bref, je suis encore à l'étape d'analyser mon problème, mais comme je ne suis encore à l'aise avec les conteneurs en C++, je voulais consulter avant de me lancer.

Donc, ce que je pensais prendre comme conteneur est un map.

Cependant, pour avoir accès aux coordonnées de rangées (i) et de colonnes (j), je voudrais rendre cela explicite. Ex : maMatrice(i,j) = 2;

Mais il ne suffira que de surchargé les opérateurs () dans ma classe Matrice.

Cependant, c'est de l'utilisation avec les maps que je ne suis pas certain.

1) Comment bien utiliser le map<int,mat<int,double>> ?
2) Est-ce mieux map<std::pair<int,int>,double> ?

Qu'en pensez-vous ?

Merci, bonne journée.

Bonjour,

Un tableau associatif, pourquoi faire ? Si tu n'accèdes à tes valeurs que via des indexs, ce n'est qu'un bête tableau bidimensionnel.

Puisqu'on est en C++, autant utiliser une abstraction plus agréable qu'un double[][] : http://www.boost.org/doc/libs/1_36_0...doc/index.html

Enfin, sache qu'il existe déjà des implémentations de matrices : http://www.boost.org/doc/libs/1_36_0.../doc/index.htm

Je pense que tu devrais jeter à coup d'oeil à comment Blitz++ a implémenté cela.

Citation:

---

Envoyé par Florian Goo

Un tableau associatif, pourquoi faire ? Si tu n'accèdes à tes valeurs que
via des indexs, ce n'est qu'un bête tableau bidimensionnel.

---

Parce que sa matrice est creuse.

Citation:

---

Enfin, sache qu'il existe déjà des implémentations de matrices :
http://www.boost.org/doc/libs/1_36_0.../doc/index.htm

---

Qui, si j'ai bonne mémoire, permet une représentation de matrice basée sur
map.

Oui, c'est pour cela que je ne peux utiliser tableaux associatifs.
Et idéalement, en gardant deux clés ordonnés, il sera facile et rapide d'accèder à la valeur.

Ex: matrice1(1,2) = 19.3, ce sera très rapide, car je serai capable d'aller voir dans un map<1,<2,...>>, ou quelque chose du genre.

Merci des références, bien apprécié.

Eh bien au temps pour moi ! Je dois bien reconnaître que je ne sais pas ce qu'est une matrice creuse.

Ce que j'affirme est ce quoi je crois, mais je peux me tromper.

Il s'agit d'une matrice dont on ne store que les éléments différents de 0.
Une Sparse Matrix en anglais, je crois.

Si j'étais dans ton cas, personnellement j'opterais plutôt pour une clé constituée de la pair(i,j). Elle est unique et traduit ce qu'elle représente. J'ai du mal à voir où serait le gain d'une double map.

Blitz++ est excellent mais n'est pas adapté aux matrices creuses.
Boost.multi_array est peu performant, et mal implémenté dès qu'on ne suit pas leur œillères en ce qui concerne les "vues" de sous-matrices (nécessité d'utiliser using boost::detail::multi_array, modèle à base de vector et d'indices {intervalles,pas}). En revanche, boost::numeric::ublas::mapped_matrix<T> semble représenter exactement ce que vous souhaitez.

Du coté des performances, les très nombreuses librairies C++ de traitement de matrices creuses (MTL, GMM++, SparseLib++/TNT, Seldon, Boost.uBlas, SCTL/ACTL, ...) prétendent toutes garder des performances raisonnables tout en faisant abstraction des détails d'implémentation de stockage. Je n'ai pas eu l'occasion de les tester personnellement à l'exception de Boost.uBlas, mais ce que je sais est que nous avons du faire une librairie maison après des comparatifs exhaustifs faits par un ingénieur, car nos matrices creuses ont des spécificités sur la diagonale et sont quasiment demi-vides (triangle supérieur seul avec faible densité loin de la diagonale).
Dans le cas général, nous utilisons Boost.uBlas, plus pour des raisons de facilité de maintenance de code que pour des raisons objectives de facilité d'utilisation ou de performance.

Je pense que pour l'implémentation d'une classe de matrice tout dépend *vraiment* de l'utilisation finale qu'on en aura...

Travailler sur de "grosses" matrices (~1000x1000) ? sur des matrices moyennes ? (~ 100x100) sur des toutes petites matrices comme en 3D (4x4 maxi)... Seront elles creuses (math-app), doivent elles être très optimisées (jeu 3D), ont elles une représentation physique, ....

Prenons par exemple, l'opération d'extraction d'une sous-matrice (fenêtre, triangularisation, inversion, déterminants, ...).
Etre capable de faire référence à une telle sous-matrice n'est pas simple (et encore moins rapide) avec des solutions à base de listes, ou map (quoique... map puisse être un poil plus adapté).
Mais encore faut-il que ces opérations soient celles recherchées.

Bon, merci tout le monde pour vos discussions.

Finalement, je vais implanter une classe element qui va contenir un unsigned int i, et un unsigned int j.

Bref, la représentation de la matrice sera une map<element,TYPE>.

Merci, bonne journeé.