vecteur des pointeurs Résolu/Fermé

Question

Bonjour, Dans un problème d'optimisation, quelle est la solution la plus meilleure pour coder une matrice d'objets? utiliser un vector> ou un vector? Autrement, quelle est la solution la plus optimisée: utiliser des objets ou des pointeurs sur objets Configuration: Windows 7 / Firefox 19.0

mamiemando · Answer

Dans l'absolu le plus efficace c'est d'utiliser un "Objet **" car dans un vector tu alloues tout ce qui est défini dans la structure template "vector" en plus de la donnée elle-même. Libre à toi d'encapsuler ce pointeur dans une structure pour mémoriser le nombre de lignes et de colonnes que tu as alloué : #include typedef struct _matrix_t { size_t num_rows; size_t num_cols; double **data; } matrix_t; Il faut juste être prudent au moment de l'allocation et de la désallocation matrix_t * new_matrix(size_t num_rows, size_t num_cols) { size_t i; matrix_t * matrix = malloc(sizeof(matrix_t); matrix->num_rows = num_rows; matrix->num_cols = num_cols; matrix->data = malloc(num_rows * sizeof(double *)); for(i = 0; i < num_rows; ++i) { matrix->data[i] = calloc(num_rows, sizeof(double)) } } void free_matrix(matrix_t * matrix) { for(i = 0; i < matrix->num_rows; ++i) { free(matrix->data[i]); } free(matrix->data); } double get_matrix(const matrix_t * matrix, size_t i, size_t j) { assert(i < matrix->num_rows); assert(j < matrix->num_cols); return matrix->data[i][j]; } Mais même là c'est pas super, car on fait pas mal de malloc et de free. Donc si vraiment on veut un truc plus efficace, on allouera directement un double * contenant num_rows * num_cols élements. Ensuite honnêtement, je pense que pour le commun des mortels, le surcoût engendré par l'encapsulation avec des vector est négligeable, à moins d'avoir vraiment beaucoup de lignes et de colonnes... #include #include typedef struct _matrix_t { size_t num_rows; size_t num_cols; double *data; } matrix_t; Il faut juste être prudent au moment de l'allocation et de la désallocation matrix_t * new_matrix(size_t num_rows, size_t num_cols) { matrix_t * matrix = malloc(sizeof(matrix_t); matrix->num_rows = num_rows; matrix->num_cols = num_cols; matrix->data = malloc(num_rows * num_cols * sizeof(double)); } void free_matrix(matrix_t * matrix) { free(matrix->data); } double get_matrix(const matrix_t * matrix, size_t i, size_t j) { assert(i < matrix->num_rows); assert(j < matrix->num_cols); return matrix->data[i * num_rows + j]; } Après, il existe des structures de données qui peuvent être plus efficaces en mémoire en fonction de la nature de ta matrice, notamment si elle contient beaucoup de zero (sparse matrix). Par exemple en C++ on pourrait définir une classe qui se base sur des maps imbriquées du genre std::map > mais l'accès serait plus lent (en O(log(n)*log(m)) au lieu de O(1)). Enfin, tu parles "d'optimisation". Je ne sais pas si c'est optimisation au sens informatique ou mathématique, mais si c'est au sens mathématique (= résoudre un problème d'optimisation) et que tu utilises une bibliothèque du genre Coin-OR tu as sans doute déjà une classe de matrice qui permettent, j'imagine, de s'abstraire de ce genre de considérations... https://www.coin-or.org/Doxygen/CoinUtils/classCoinPackedMatrix.html De même, boost fournit une structure de matrice template, ce qui t'évitera de réinventer la roue (accessoirement vu le niveau des gens qui programment boost, tu peux l'utiliser en toute confiance :p) : https://www.boost.org/doc/libs/1_42_0/libs/numeric/ublas/doc/matrix.htm Bonne chance

kochfet · Answer

OK merci mamiemando pour la réponse. Mais dans mon code le nombre des lignes et le nombre des colonnes ne sont pas connus qu'à l'exécution.
Aussi la matrice contient des objets qui sont des instances d'une classe mère ou des instances des classes filles héritées de cette classe mère. 
Autre chose mon code est en C++.

mamiemando · Answer

Mais dans mon code le nombre des lignes et le nombre des colonnes ne sont pas connus qu'à l'exécution. Oui et justement, la fonction qui alloue une matrice prend ces deux valeurs en paramètre, donc tu peux définir sa taille à l'exécution. La seule supposition, c'est que tu saches déterminer sa taille juste avant de l'allouer. Aussi la matrice contient des objets qui sont des instances d'une classe mère ou des instances des classes filles héritées de cette classe mère. À la place de stocker un double * tu peux utiliser un pointeur vers ton type. Ou encore mieux faire une matrice template... template struct matrix_t { size_t num_rows; size_t num_cols; T *data; }; Autre chose mon code est en C++. Je ne vois pas où est le problème (inclue simplement , et à la place), le code reste juste. Ceci dit on aura tendance à définir des méthodes et des constructeurs pour être plus dans le paradigme objet, mais ça n'engendre que des changements mineurs sur le code. #include #include #include template class matrix_t { private: size_t num_rows; size_t num_cols; T *data; public: matrix_t(size_t num_rows0, size_t num_cols0): num_rows(num_rows0), num_cols(num_cols0), { matrix->data = malloc(num_rows * num_cols * sizeof(T)); } ~matrix_t() { free(this->data); } inline size_t get_num_rows() const { return this->num_rows; } inline size_t get_num_cols() const { return this->num_cols; } const T & get_value(size_t i, size_t j) const { assert(i < this->get_num_rows()); assert(j < this->get_num_cols()); return this->data[i * num_rows + j]; } }; Bonne chance

kochfet · Answer

Merciiiiii Mais juste une autre question : Que peut on faire si le nombre des lignes et le nombre des colonnes est inconnu même à l'exécution. Est ce qu'on recourt à utiliser le vector ? Dans le cas général : Quelle est la différence entre : 1) C** tab 2) vector< vector <* C> > C est une classe

mamiemando · Answer

La seule chose que tu peux faire c'est faire un realloc (si tu as fait des malloc) ou des resize/push_back si tu utilises des std::vector. Dans le cas général : Quelle est la différence entre : 1) C** tab 2) vector< vector <* C> > 1) C'est l'adresse d'un pointeur de type C *, ce pointeur étant l'adresse d'un C. Les pointeurs sont fréquemment utilisés pour viser le premier élément d'un tableau d'élément (un plop_t * désigne alors un tableau de plop). Si tu itères ce raisonnement, tu peux faire un tableau de tableau de plop_t en allouant correctement un plop_t ** (tableau 2D) et pourquoi pas un plop_t **** (tableau 3D) etc. 2) Déjà je pense que tu veux plutôt parler d'un vector > et à ce moment là pourquoi ne pas manipuler directement un vector > si C est de petite taille et/ou si la "matrice" est petite, ce sera plus simple à allouer/manipuler. Dans ce second cas la classe vector est une classe template qui embarque un T* plus quelques informations additionnelles (la taille du vector, la taille réservée, etc). Pour plus de détails tu peux regarder le header . C'est donc un peu plus coûteux en mémoire même si en pratique à mon avis c'est relativement négligeable. En terme de performance, les deux solutions se valent (accès en O(1) à chaque élément du tableau). Dans les deux cas un realloc/resize peut dégrader les performances (c'est pour ça d'ailleurs que la méthode reserve est définie dans la classe vector). http://www.cplusplus.com/reference/vector/vector/ Bonne chance

kochfet · Answer

Merciiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii

mamiemando · Answer

Je t'en prie, bonne continuation ;-)

Vecteur des pointeurs

7 réponses

Discussions similaires