Discussion :

[Happpy]

Bonjour tout le monde, je suis en train de gérer ma map grâce à une classe Carte.

J'utilise ce code

Code :

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

vector < vector < CaseCarte > > m_CaseCarte;

afin de gérer chaque case. Malheureusement, quand on utilise une vector, une copie de l'objet est créee en mémoire. Je vais faire court, avec une carte de 10 * 10 cases, sachant que je map sous trois couches (trois sprites par cases), 300 sf::sprite sont utilisés... ça fait beaucoup.

Je n'ai pas de ralentissement, la map charge et s'affiche en moins d'une demie seconde.
J'aimerai faire de l'économie de mémoire et manipuler les cases avec ce code :

Code :

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

vector < vector < shared_ptr <CaseCarte> >> m_CaseCarte;

Mais comment faire pour initialiser correctement chaque pointeur dans le vector à deux dimensions ?

Merci D'Avance.
Au Revoir.

[koala01]

Salut,

Et, si, au lieu de gérer un tableau à deux dimensions de 10*10 éléments, tu gérais un tableau à une seule dimension de... 100 éléments

La "formule" pour savoir quel élément se trouve où serait de l'ordre de

Code :

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

position = (ligne_recherchée * nombre_de_lignes ) + colone_recherchée

Cela t'éviterait d'avoir des copies de vecteur, et te simplifierait la tâche

Tu en arriverait donc à quelque chose de fort proche de

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
class Map
{
    public:
        shared_ptr <CaseCarte> * element(int line, int column)
        {
            return items_[line * 10 + column];
        }
        void read(std::string const & filename)
        {
            std::ifstream ifs(filename.c_str());
            for(int line = 0; line <10; ++line)
           {
               for(int column = 0;column < 10; ++column)
               {
                   // lecture des sprites et insertion dans items_
               }
           }
        }
    private:
        std::vector<shared_ptr <CaseCarte> > items_;
};

[bertry]

Salut,

Malheureusement, quand on utilise une vector, une copie de l'objet est créee en mémoire.

Si par "utiliser un vector" tu veux dire le donner comme argument à une fonction, alors pour éviter la copie de l'objet, tu peux le transmettre par référence :

Code :

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

void MaFonction ( const vector < vector < CaseCarte > >& MaCaseCarte )

Sinon,

Et, si, au lieu de gérer un tableau à deux dimensions de 10*10 éléments, tu gérais un tableau à une seule dimension de... 100 éléments

Ce conseil est très pertinent, suis le. J'ai été confronté à un problème d'extrême lenteur pour les même raison ( si le sujet t'intéresse voici l'adresse du post dans le forum ), la solution était d'utiliser un vector à une dimension plutôt qu'un vector de vector

[Happpy]

Abon, donc en utilisant un vector de vector, on perd obligatoirement en rapidité ?

[JolyLoic]

On gagne en souplesse (souvent malvenue dans ce genre de situation : On peut avoir des tailles différentes sur chaque ligne), mais on perd généralement en rapidité.

A part si la taille est très importante, et qu'allouer tout d'un bloc pourrait poser des problèmes, j'utiliserais systématiquement un seul vecteur.

[Happpy]

Ah ok d'accord. Oui.

C'est vrai qu'avec un vector à 1 dimensions, je pourrais facilement utiliser les pointeurs classique (en n'oubliant pas les delete dans le destructeur) et le seul vector sera plus facilement manipulable.

Je vous tiens au courant pour la transposition 2D - 1D.

[authchir]

Sinon, il y a aussi boost::multi_array (http://www.boost.org/doc/libs/1_47_0.../doc/user.html) qui semble adapté à ce genre de situation.

[jblecanard]

Ah ok d'accord. Oui.

C'est vrai qu'avec un vector à 1 dimensions, je pourrais facilement utiliser les pointeurs classique (en n'oubliant pas les delete dans le destructeur) et le seul vector sera plus facilement manipulable.

Je vous tiens au courant pour la transposition 2D - 1D.

Je vois pas trop en quoi ça change quelque chose. Dans les deux cas, tu peux prendre des pointeurs classiques ou des sahred_ptr, selon ton besoin.

[Happpy]

Oui mais c'est juste pour le ralentissement provoqué par le tableau 2D (dit ci-dessus)...

Alors que dois-je faire finalement ?

[jblecanard]

Alors que dois-je faire finalement ?

Ben... comme tu veux ! Le choix du type de pointeur est une problématique différente de celle du choix de la structure sous jacente à ton tableau.

[Happpy]

Bon ben je cite :

JolyLoic :
On gagne en souplesse (souvent malvenue dans ce genre de situation : On peut avoir des tailles différentes sur chaque ligne), mais on perd généralement en rapidité.

A part si la taille est très importante, et qu'allouer tout d'un bloc pourrait poser des problèmes, j'utiliserais systématiquement un seul vecteur.

Je vais tout simplement utiliser une vector à 1 dimensions avec pointeur pour gagner en vitesse comme JolyLoic le dit. J'aurai utilise boost::multy_array mais comme les tableaux à deux dimensions font perdre en vitesse...

[Flob90]

Tu peux utiliser boost::multy_array, j'ai jamais regarder l'implémentation mais c'est probablement optimisé pour être rapide : l'interface offre un tableau à plusieurs dimension mais l'implémentation est un tableau unidimensionnel (stockage NRC peut-être).

[jblecanard]

Je vais tout simplement utiliser une vector à 1 dimensions avec pointeur pour gagner en vitesse comme JolyLoic le dit.

Bien sûr, il y a un malentendu : je croyais que tu te demandais quoi choisir entre pointeur et shared_ptr.

[Happpy]

Oui mal-entendu ^^

Car quand j'utilise ce code :

Code :

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

1
2
 
std::vector < std::vector <CaseCarte*> > m_CaseCarte;

En faisant les allocations dynamiques nécessaires....

Et en utilisant ce code :

Code :

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

1
2
 
std::vector < std::vector <CaseCarte> > m_CaseCarte;

Les deux codes utilisent le même quantité de mémoire, alors que ça ne devrait pas être le cas avec le pointeur non ?

Enfaite, j'aimerai savoir comment optimiser afin d'utiliser le moins de mémoire tout en ayant un maximum de vitesse... et avoir confirmation que l'utilisation d'un vector à 1 dimension est plus rapide que l'utilisation de celui à deux dimensions.

[koala01]

Oui mal-entendu ^^

Car quand j'utilise ce code :

Code :

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

1
2
 
std::vector < std::vector <CaseCarte*> > m_CaseCarte;

En faisant les allocations dynamiques nécessaires....

Et en utilisant ce code :

Code :

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

1
2
 
std::vector < std::vector <CaseCarte> > m_CaseCarte;

Les deux codes utilisent le même quantité de mémoire, alors que ça ne devrait pas être le cas avec le pointeur non ?

Absolument pas...

Au pire, tu aurais sans doute une (très légère) augmentation de la mémoire totale utilisée en utilisant un std::vector< std::vector <CaseCarte * > > car il faut, en plus de stocker la caseCarte, en stocker l'adresse (soit, 4 à 8 bytes par case à maintenir).

Cependant, il faut garder en mémoire que l'insertion dans une collection se fait systématiquement par copie.

Or, la copie de CaseCarte peut s'avérer couteuse, si tant est qu'elle aie seulement un sens, ce qui ne sera surement pas le cas si CaseCarte est une classe de base dans une hiérarchie d'héritage publique, alors que la copie de pointeur (je parle bien de copier l'adresse représentée par un pointeur dans un autre pointeur et non de copier le contenu de ce qui est pointé par le pointeur ) est beaucoup plus rapide (ce n'est qu'une valeur codée sur 4 ou 8 bytes )

Enfaite, j'aimerai savoir comment optimiser afin d'utiliser le moins de mémoire tout en ayant un maximum de vitesse... et avoir confirmation que l'utilisation d'un vector à 1 dimension est plus rapide que l'utilisation de celui à deux dimensions.

Tout dépendra de comment tu insere tes éléments dans ton vecteur à deux dimensions:

Si tu remplis un vecteur avant de le placer dans ton vecteur de vecteur, tu te payera une copie de ton (pointeur sur ) élément CaseCarte lors du remplicage du vecteur et une autre lorsqu'il sera question d'insérer le vecteur dans le vecteur de vecteur car il y aura copie du vecteur et donc de son contenu.

Si tu insere tes vecteurs vides dans ton vecteur de vecteur et que tu n'insere tes (pointeurs sur) élément CaseCarte qu'après, tu gagnera un peu lors du remplissage.

En outre, tu gagnera sans doute en terme de cache si tu travaille avec un vecteur une dimension, parce que la caractéristique première d'un std::vector est... de maintenir les différents éléments de manièr contigue en mémoire.

Enfin, il faut garder en mémoire qu'un std::vector présente une utilisation de la mémoire un peu plus importante que celle d'un simple array "C style", car il doit entre autre garder en mémoire des information permettant de retrouver sa taille et / ou le dernier élément utilisé dans l'espace mémoire qui lui est alloué.

Tout cela pour en arriver aux conclusions que:

• De toutes manière, l'utilisation d'un std::vector à une dimension est préférable à celle d'un std::vector de std::vector, à moins que tu n'aies de très nombreux éléments à maintenir en même temps
• Il sera sans doute préférable d'utiliser un std::vector de pointeurs (éventuellement intelligents) sur CaseCarte si la copie de CaseCarte risque de prendre du temps
• Il sera de toutes façons indispensable d'utiliser un std::vector de pointeurs (éventuellement intelligents) sur CaseCarte si CaseCarte intervient dans une hiérarchie d'héritage

[ac_wingless]

Juste une petite remarque pour ceux qui conseillent boost:multi_array: dans le cas général, c'est une très bonne idée de conseiller boost pour résoudre un problème classique.

Sauf pour boost::multi_array.

C'est probablement la sous-librairie la plus médiocre de tout boost. Elle est peu lisible, le travail avec des sous-tableaux (array_view) est pénible, mais surtout les itérateurs ne sont pas pensés pour la performance en termes de cache (un comble pour une classe prévue pour la manipulation de matrices): il est impossible de définir l'arrangement en mémoire! En gros, cette librairie est à déconseiller en dehors des cas les plus simples, où il s'agit de définir les dimensions à l'exécution par boost::extents et ensuite d'accéder par [] à chaque indice, sans se préoccuper de performance.

Je ne suis pas sûr que la question initiale implique le recours à des librairies scientifiques performantes, mais en tout cas boost::multi_array me semble moins adaptée que quelques pages faites à la main, comme par exemple une contribution de r0d.