Discussion :

[darkman19320]

Bonjour tout le monde,

J'essaye de faire un vecteur d'objet connaissant leur voisins (qui ne sont pas forcément à l'indice précédent).

Pour cela, j'ai fait une structure de noeud contenant des données, le pointeur sur le noeud précédent et le noeud suivant:

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
22
23
24
25
26
27
28
29
30
 
#include <vector>
#include <iostream>
using namespace std;
 
struct Data
{
	double m_val;
	int m_id;
 
	Data(): m_val (0), m_id(-1)
	{
	}
 
	virtual ~Data()
	{
	}
 
};
 
struct Node
{
	Data* m_data; //des données contenant un id
	Node* m_next; // le noeud précédent
	Node* m_prev; // le noeud suivant
 
	Node(): m_data(NULL), m_next(NULL), m_prev(NULL)
	{
	}
};

Jusque là rien d'extraordinaire.

Ensuite, je fais une autre structure contenant une tête et une queue ainsi qu'un vecteur de Node.

Quand j'insère un objet Data, je crée un nouveau Node et je l'ajoute à celui ci et je mets à jours les différents Node.

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
struct Graph
{
	Node* m_head; 
	Node* m_tail;
 
	std::vector<Node> m_nodes;
 
	Graph(): m_head(new Node()), m_tail(new Node())
	{
               //Creation d'un graph fermé bouclant aux extrémités
 
		m_head->m_next = m_tail;  
		m_head->m_prev = m_head;
 
		m_tail->m_prev = m_head;
		m_tail->m_next = m_tail;
	}
 
        virtual ~Graph()
        {
              delete m_head;
              delete m_tail;
        }
 
	void insert(Data* data)
	{
		if (data != NULL)
		{
			data->m_id = m_nodes.size();
			m_nodes.push_back(Node());
 
			m_nodes[data->m_id].m_data = data;
 
			m_nodes[data->m_id].m_next = m_tail;
			m_nodes[data->m_id].m_prev = m_tail->m_prev;
 
                        // lors du premier ajout, m_tail->m_prev correspond à m_head
			m_tail->m_prev->m_next = &(m_nodes[data->m_id]);
			m_tail->m_prev = &(m_nodes[data->m_id]);
		}
	}
};

Voici un exemple d'utilisation:

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
 
int main(int argc, char **argv) {
 
	Graph g;
	Data d, d1, d2;
 
	g.insert(&d);
	g.insert(&d1);
	g.insert(&d2);
 
        if (g.m_nodes[0].m_next == &(g.m_nodes[1]))
        {
             cout << "C'est ok" << endl;
        } else 
        {
             cout << "Tu t'es planté" << endl;
        }
	return 0;
}

Mon problème est que je n'obtiens pas le bon résultat ("C'est ok").
Pire encore, lorsque je tente d'accéder aux données du Noeud 1 à partir du Noeud 0 (g.m_nodes[0].m_next->m_data) j'ai une belle erreur de segmentation alors que lorsque je n'ai pas de problèmes lorsque j'accède directement à ces données à partir du noeud 1 (g.m_nodes[1].m_data)...

J'ai remarqué que les adresses des Node stockés dans le vecteurs changeaient au cours de l'insertion de nouveau Node.

Est-ce normal?

Comment remédier à ce problème (sans remplacer des Nodes par des pointeurs de Node au niveau du vecteur)?

Merci pour tout!

[Neckara]

Bonjour,

Essayes plutôt de stocker des pointeurs dans ton vecteur.

Le vecteur n'est pas magique, il alloue un espace mémoire et range les éléments consécutivement en mémoire dans cet espace.
Lorsqu'on insert un nouvel élément et qu'il n'y a plus de place (ou lorsqu'on fait un reserve), il va demander à l'OS (?) de réserver une place plus grande.
Dès lors il y a deux possibilités :
- soit il y a de la place disponible juste après l'espace alloué ou l'OS avait réservé un peu plus de place que nécessaire et dans ce cas là aucun déplacement n'est effectué ;
- soit l'OS réserve un espace plus grand ailleurs en mémoire et on copie tout le contenu du vecteur d'où le fait que les adresses de tes éléments changent.

C'est pour cela qu'il est beaucoup plus optimisé de faire un réserve (quand on connaît le nombre d'élément final/maximal du vecteur) dans un vecteur avant de le remplir afin de réserver l'espace mémoire une seule fois et de s'éviter un pas mal de copie.

[darkman19320]

Merci pour ta réponse.

Justement j'essaye d'éviter à devoir stocker des pointeurs pour que mes données soient proche "physiquement".

On m'a assuré que les temps d'accès soient raccourcis (bien que je n'y croie guère...)

[koala01]

Salut

Justement j'essaye d'éviter à devoir stocker des pointeurs pour que mes données soient proche "physiquement".

On m'a assuré que les temps d'accès soient raccourcis (bien que je n'y croie guère...)

En effet, si tu arrives à éviter les "cache misses", il y a des chances pour que les temps d'accès soient améliorés.

Pour rappel, la mémoire est généralement subdivisée en "pages" qui correspondent à un ensemble d'adresses mémoire "directement accessibles".

Si l'adresse à laquelle se trouve un des éléments dont tu as besoin ne se trouve pas sur la page mémoire sur laquelle le processeur se trouve actuellement, il devra... passer à la bonne page, un peu comme ce qui se passe quand tu lis un livre.

Le passage de page en page prend, effectivement, un peu de temps et si tu dois passer à une autre page pour accéder à la donnée suivante à chaque fois que tu as lu une donnée, cela peut, effectivement, finir par augmenter considérablement les temps d'accès aux données, quand tu as affaire à un volume de données très important

Le problème, c'est que la seule structure de taille dynamique qui te donne la garantie que les données sont contigües en mémoire est le tableau ( faisons simple : std ::vector )

Seulement, pour te donner cette garantie, cette structure devra régulièrement déplacer les données au moment de l'insertion (parce qu'il n'y a plus de place pour rajouter une donnée juste après la dernière, parce qu'il faut bien "faire de la place" pour rajouter une donnée entre deux, ...) ou au moment de la suppression (parce qu'il faut bien "combler le vide" laissé par la donnée supprimée).

Dans le cas de ta structure node, chaque fois que les données seront déplacées en mémoire, les relations entre les différents node seront, d'office, invalidées (fatalement : un objet qui se trouve à l'adresse XXX avant d'être déplacé ne s'y trouve plus une fois qu'il a été déplacé, ca semble logique, non )

Tu n'as donc pas beaucoup de possibilités pour résoudre ce genre de problème:

Soit tu fais en sorte que chaque node créé reste à une adresse que tu peux considérer comme définitive (c'est ce que Nekara te conseille). Cela dégradera peut etre (*) un peu les performances en terme d'accès aux données, mais te facilitera énormément la vie

Soit tu mets en place un système qui va re générer l'ensemble des relations entre tes nodes à chaque fois qu'il auront été déplacés. Cela te fera peut etre (*) gagner en performances en terme d'accès aux données, mais ralentira énormément l'insertion et te compliquera considérablement la vie

(*) j'insiste sur le peut être parce qu'il faudrait faire des tests répétés pour voir dans quelle mesure les performances sont impactées. Mais préfères tu, dans un premier temps, avoir quelque chose qui fonctionne même si c'est perfectible en terme de performance, ou avoir quelque chose de rapide qui ne fonctionne visiblement pas

Ce que tu essayes de faire pour l'instant s'apparente fortement à de l'optimisation prématurée ! Si je peux te donner un conseil: avant d'essayer d'avoir quelque chose de rapide, essayes déjà d'avoir quelque chose qui fonctionne, puis, vois comment en améliorer les performances, si (et seulement si!!!) tu estimes qu'elles ne sont pas telles qu'elles devraient être

[darkman19320]

Merci pour ta réponse très bien détaillée.

Il est vrai que j'ai potentiellement beaucoup de données et que notre principale contrainte est le temps d'insertion qui doit être constant.

Donc je vais partir dans un premier temps sur la version avec les pointeurs puis si j'ai le temps faire des tests pour voir si l'utilisation des objets est "meilleur" en temps d'accès.

Encore merci.

[JolyLoic]

Autre possibilité : Stocke dans tes données non pas les pointeurs sur tes voisins, mais les indices de tes voisins dans le vector. Il s'agit là d'une donnée stable.

[koala01]

Autre possibilité : Stocke dans tes données non pas les pointeurs sur tes voisins, mais les indices de tes voisins dans le vector. Il s'agit là d'une donnée stable.

... du moins, tant que tu ne supprimes pas de noeuds (mais il est vrai que, a priori, ca n'arrive pas souvent )