Idée sur un graphe

**azamharir** · 24/11/2007, 20h58

salut
je dois implementer un graphe (graphe : cas général). je cherche la meilleure structure possible.
je crois que je vais utiliser celle ci :

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
une classe noeud
{
    contient l'information du noeud (nom ...)
    un suivant de type poids* (en fait c'est une liste de poids* et suivant est 
    la tete de cette liste)
}
 
une classe poids
{
    contient un le cout ou poids (un entier ou float ..., c'est le poids d'une 
    arete)
    un frere de type poids* (en fait c'est une liste de poids* qui partent du 
    meme noeud)
    un suivant de type noeud* (c'est le noeud d'arrivée de l'arete qui possede 
    ce poids)
}

que pensez vous de cette démarche?
j'attends vos remarques, merci et à bientot

**loufoque** · 24/11/2007, 22h16

boost::graph

**azamharir** · 24/11/2007, 22h30

merci loufoque,
mais je prefere le programmer moi meme. en plus, c'est pour un gros graphe (reseau routiers, ... c'est des graphes à l'echelle des villes). En plus, j'ai des algorithmes à appliquer et je dois jongler entre la ram et le disque pour ne pas saturer la mémoire.
donc, utiliser boost (je crois) n'est pas une solution pour moi.
merci, et si tu as d'autres conseils, je suis preneur. @++

**Kujara** · 25/11/2007, 09h59

Pas d'accord pour le coup de la liste.
Si tu a tendance a etre limité par la ram, utilise plutot un tableau de base( la liste stoque des pointeurs de plus). Par contre tu y perds grandement si tu a besoin de rajouter / enlever des noeuds.
Mais bon, si c'est pour une carte routiere,ce n'est clairement pas le cas...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
struct Node;
struct Link
{
float poids;
Node * node;
};
 
struct Node
{
Link * links;
unsigned int numLinks;
//suivit des infos supplementaires par node.
};

Remplace les links par un std::vector si tu veux, mais tu va y perdre en mémoire, pour y gagner en facilité de code ( de peu). A toi de voir.

**zais_ethael** · 25/11/2007, 12h19

Envoyé par Kujara

Remplace les links par un std::vector si tu veux, mais tu va y perdre en mémoire, pour y gagner en facilité de code ( de peu). A toi de voir.

Serais-ce une vile tentative pour inciter aux mauvaises techniques de programmation?? Tu te rends compte du faible nombre d'informations supplémentaires que rajoute un std::vector par rapport à un tableau C-style? A priori, ça rajoute uniquement un size_t (et pas un unsigned int) pour indiquer la capacité qui est d'ailleurs bien utile pour l'optimisation vitesse.

**Kujara** · 25/11/2007, 14h16

Envoyé par zais_ethael

Serais-ce une vile tentative pour inciter aux mauvaises techniques de programmation?? Tu te rends compte du faible nombre d'informations supplémentaires que rajoute un std::vector par rapport à un tableau C-style? A priori, ça rajoute uniquement un size_t (et pas un unsigned int) pour indiquer la capacité qui est d'ailleurs bien utile pour l'optimisation vitesse.

"sizeof(vector<int>)" 16, contre 8 pour un tableau de base + taille.
Quand on est limité par la mémoire, ça compte,surtout pour des tableaux de faible taille, genre 2 ou 3 elements, comme on risque de voir ici.

Quand au size_t, apprends que c'est soit un unsigned int, soit un unsigned __int64.

la version 64 se justifie uniquement sur architecture 64, où justement, unsigned int vaut lui aussi unsigned __int64.

Donc, j'utilise unsigned int.

**koala01** · 25/11/2007, 15h01

Salut,

Envoyé par Kujara

"sizeof(vector<int>)" 16, contre 8 pour un tableau de base + taille.
Quand on est limité par la mémoire, ça compte,surtout pour des tableaux de faible taille, genre 2 ou 3 elements, comme on risque de voir ici.

(snip)

Oui, mais bon... faut pas exagérer non plus...

Si tu perd, effectivement, l'équivalent de 8 caractères pour un tableau, cela reste indépendant de la taille du tableau, et donc, tu ne perd donc que 8000 caractères (même pas 8k de mémoire) pour... 1000 tableaux ...

Au pire, si tu utilise un std::vector<int>, tu perd plus de place sur chaque tableau à rajouter deux éléments à ton tableau "C style" qu'à utiliser un std::vector...

Alors, je suis d'accord que la mémoire n'est pas extensible, et tout ce que tu veux...

Mais il n'empêche que le temps où il n'y avait que 64 ko de mémoire est révolu depuis longtemps et que tu atteindra sans doutes les limites de ton système à d'autres points de vue (sur des systèmes limités en mémoire) bien avant d'atteindre les limites mémoire du simple fait que tu as préféré utiliser un std::vector...

Dés lors - mais ce n'est qu'un avis perso, même si j'aurais tendance à considérer ceux qui n'y adhèrent pas comme mazochistes - je préfère parier sur la sécurité et sur la facilité, sur ce coup là...

**Kujara** · 25/11/2007, 15h10

Envoyé par koala01

Dés lors - mais ce n'est qu'un avis perso, même si j'aurais tendance à considérer ceux qui n'y adhèrent pas comme mazochistes - je préfère parier sur la sécurité et sur la facilité, sur ce coup là...

Je suis d'accord avec toi sur le principe, puisque les tableaux sont plus faciles a foirer, mais je te cite l'auteur du message :

En plus, j'ai des algorithmes à appliquer et je dois jongler entre la ram et le disque pour ne pas saturer la mémoire

Problemes de ram -> optimisation mémoire, non ?

Si tu perd, effectivement, l'équivalent de 8 caractères pour un tableau, cela reste indépendant de la taille du tableau, et donc, tu ne perd donc que 8000 caractères (même pas 8k de mémoire) pour... 1000 tableaux ...

2 elements par tableaux, mettons 2 pointeurs. 2 * 4 + 8 d'un coté, 2*4 + 16 de l'autre, tu economise 33% de mémoire. Ca vaut le coup ^^.

Apres, c'est sur que si la taille moyenne est beaucoup plus grande, c'est pas la peine.
Et puis utiliser std::vector quand tu connais la taille d'avance, et que tu n'enleve / n'ajoute jamais d'elements en temps réel, c'est un peu useless.
Les tableaux de base, correctement utilisés, ne sont pas plus dangereux.

**Médinoc** · 25/11/2007, 15h13

koala01+1.
8 octets pour la sécurité qu'ils apportent, c'est un cout négligeable. Même sur une calculatrice.

Envoyé par Kujara

Quand au size_t, apprends que c'est soit un unsigned int, soit un unsigned __int64.

la version 64 se justifie uniquement sur architecture 64, où justement, unsigned int vaut lui aussi unsigned __int64.

Donc, j'utilise unsigned int.

Qu'est-ce que c'est que ce raisonnement, non seulement pourri mais basé sur une idée fausse ?

size_t est LE type pour les tailles et les indexes de tableau, puisqu'il doit avoir la taille du plan mémoire. C'est donc LE type approprié, et il n'est jamais plus grand que nécessaire.
Et non, sous Win64, un unsigned int ne fait pas 64 bits. Ni même un unsigned long. Seul un unsigned __int64 (ou unsigned long long) fait tout le temps 64 bits. Et boum! Une erreur qui aurait pu être évitée si tu avais tout simplement utilisé un size_t...

**koala01** · 25/11/2007, 15h24

Envoyé par Kujara

Je suis d'accord avec toi sur le principe, puisque les tableaux sont plus faciles a foirer, mais je te cite l'auteur du message :

Problemes de ram -> optimisation mémoire, non ?

2 elements par tableaux, mettons 2 pointeurs. 2 * 4 + 8 d'un coté, 2*4 + 16 de l'autre, tu economise 33% de mémoire. Ca vaut le coup ^^.

Mais, avant de vouloir optimiser la mémoire à coup de 8 octets, tu ne crois pas qu'il y aurait largement intérêt à essayer d'optimiser les choses qui... en valent vraiment la peine (je sais pas, moi... essayer de trouver un endroit où tu en gagnera directement 100 ou 200

)

Et puis utiliser std::vector quand tu connais la taille d'avance, et que tu n'enleve / n'ajoute jamais d'elements en temps réel, c'est un peu useless.
Les tableaux de base, correctement utilisés, ne sont pas plus dangereux.

Si tu as la certitude que tu auras en permanence N éléments dans ton tableau, ni plus, ni moins... oui...

Mais, dés le moment où tu te trouve dans une situation où le nombre d'éléments peut varier ne serait-ce que de 1 ou deux, tu devra déclarer ton tableau avec... la taille maximale potentielle, et tu perdra d'un seul coup tout le bénéfice de la chose sur les tableaux qui ne sont pas complètement remplis... Et cela peut même aller jusqu'à une perte énorme de mémoire... (imagine simplement un tableau de taille maximale de 4 éléments, mais une moyenne de 2 éléments dans le tableau et tu es en négatif

)

Non, décidément, j'aurais tendance à utiliser le std::vector, et à réfléchir plutôt à l'organisation optimale des séquence d'accès disque par rapport aux séquences d'acces mémoire

**Kujara** · 25/11/2007, 15h26

Envoyé par Médinoc

[*]Et non, sous Win64, un unsigned int ne fait pas 64 bits. Ni même un unsigned long. Seul un unsigned __int64 (ou unsigned long long) fait tout le temps 64 bits. Et boum! Une erreur qui aurait pu être évitée si tu avais tout simplement utilisé un size_t...

Ah tiens, je croyais.

Ok, méa culpa alors ^_^.

Envoyé par Médinoc

koala01+1.
8 octets pour la sécurité qu'ils apportent, c'est un cout négligeable. Même sur une calculatrice.

Ca par contre, non.

Si vous savez programmer, il n'y a pas de probleme de securité... Partez voir les milliards de lignes de code ecrites en C qui ne crashent jamais alors qu'ils utilisent des tableaux de base...

D'autant plus que c'est tout aussi facile de sortir d'un vector que de sortir d'un tableau, puisque l'operateur [] ne verifie pas les index...
Et oui, at() ça existe, mais apparemment 1) c'est pas assez connu 2) c'est plus lent.

Enfin bref, j'avoue que conseiller d'utiliser les tableaux de base a n'importe qui, c'est mal, c'est pour ça que je le fait jamais, sauf dans les cas où l'auteur a clairement besoin d'optimiser la mémoire...

**Kujara** · 25/11/2007, 15h32

Envoyé par koala01

Mais, avant de vouloir optimiser la mémoire à coup de 8 octets, tu ne crois pas qu'il y aurait largement intérêt à essayer d'optimiser les choses qui... en valent vraiment la peine (je sais pas, moi... essayer de trouver un endroit où tu en gagnera directement 100 ou 200

)

Certes. Mais si son graph est enorme( beaucoup de nodes et peu d'arretes par node), tu va y gagner beaucoup plus a coup de 8 octets par node que 200 octets sur un objet crée une fois.

Apres, faut voir le reste de son probleme bien sur, mais avec ce qu'il nous a donné comme infos, ça parait viable.

Mais, dés le moment où tu te trouve dans une situation où le nombre d'éléments peut varier ne serait-ce que de 1 ou deux, tu devra déclarer ton tableau avec... la taille maximale potentielle, et tu perdra d'un seul coup tout le bénéfice de la chose sur les tableaux qui ne sont pas complètement remplis... Et cela peut même aller jusqu'à une perte énorme de mémoire... (imagine simplement un tableau de taille maximale de 4 éléments, mais une moyenne de 2 éléments dans le tableau et tu es en négatif

)

..... je parlais de tableaux dynamiques alloués a la taille utilisé, pas de tab[N].
Donc zero pertes, guaranti.

Non, décidément, j'aurais tendance à utiliser le std::vector, et à réfléchir plutôt à l'organisation optimale des séquence d'accès disque par rapport aux séquences d'acces mémoire

Ca optimise la vitesse, ça, pas la mémoire utilisé.
Mais si il sait d'avance que ça va bouffer toute la ram, effectivement mon optim deviens inutile et la tienne est beaucoup plus importante.

**koala01** · 25/11/2007, 15h42

Envoyé par Kujara

<snip>

Si vous savez programmer, il n'y a pas de probleme de securité... Partez voir les milliards de lignes de code ecrites en C qui ne crashent jamais alors qu'ils utilisent des tableaux de base...

D'autant plus que c'est tout aussi facile de sortir d'un vector que de sortir d'un tableau, puisque l'operateur [] ne verifie pas les index...
Et oui, at() ça existe, mais apparemment 1) c'est pas assez connu 2) c'est plus lent.

Mais les vector ont quelque chose que n'ont - à la base - les tableaux C style, même si, en pratique, on l'implémente régulièrement: la la taille du tableau...

Dés lors, bien sur que le code C

Code :

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

1
2
3
4
5
 
for(i=0;i<tabsize;i++)
{
    /* n'importe quel acces à tab[i] si tabsize est la taille du tableau */
}

fonctionnera exactement de la même manière que le code C++

Code :

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

1
2
3
4
for(i=0;i< tab.size();i++)
{
    /* n'importe quel acces à tab[i]; */
}

mais, encore une fois, si tu dois maintenir "quelque part" la taille de chaque tableau, parce qu'ils peuvent avoir des taille ne serait-ce que légèrement différente (de l'ordre de un ou deux élément(s) en plus ou en moins), autant que cette information soit directement liée au tableau, et non, qu'elle soit "perdue" dans la masse des autres informations non spécifiques au tableau

Maintenant, pour la méthode at()... c'est une autre histoire

[/QUOTE]
Enfin bref, j'avoue que conseiller d'utiliser les tableaux de base a n'importe qui, c'est mal, c'est pour ça que je le fait jamais, sauf dans les cas où l'auteur a clairement besoin d'optimiser la mémoire...[/QUOTE]
Je le redis, avant de vouloir optimiser la mémoire à coup de 8 octets, autant essayer de l'optimiser à coup plus importants...

Et j'ai la certitude que le simple fait de gérer correctement les étapes d'acces disque et d'acces mémoire, dans le cas qui intéresse le PO, aura un impact bien plus grand que celui fournit par la proposition que tu fais

**koala01** · 25/11/2007, 15h47

Envoyé par Kujara

(snip)
..... je parlais de tableaux dynamiques alloués a la taille utilisé, pas de tab[N].
Donc zero pertes, guaranti.

Sauf que, dés le moment où tu parle de tableau alloués dynamiquement, il te faudra quand même maintenir la taille du tableau quelque part...

Dés lors, cela revient exactement au même que d'utiliser un std::vector (cf ma réponse précédente, car les deux se sont croisées

)

Ca optimise la vitesse, ça, pas la mémoire utilisé.
Mais si il sait d'avance que ça va bouffer toute la ram, effectivement mon optim deviens inutile et la tienne est beaucoup plus importante.

Ca peut très bien optimiser la mémoire également, si on prend le temps de faire le ménage nécessaire avant de recommencer une séquence d'acces disque

Je reconnais volontiers cependant que c'est fortement dépendant de plein de choses, dont, entre autres, le fait qu'il soit possible de faire le "ménage" sur les noeuds devenus inutiles

**Kujara** · 25/11/2007, 16h06

Aller, mon dernier message pour ce sujet, ça commence a trop deriver

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
template<typename T>
class Array
{
private:
	T * m_datas;
	size_t m_size;
public:
	Array( size_t p_size)
		:	m_size( p_size)
	{
		m_datas = new T[p_size];
	}
	~Array( )
	{
		delete [] m_datas;
	}
 
	T & operator[](size_t p_index)
	{
		return m_datas[p_index];
	}
 
	T & at( size_t p_index)
	{
		if (p_index>=m_size)
		{
			throw std::out_of_range("invalid Array<T> subscript");
		}
		return m_datas[p_index];
	}
	size_t size()const{return m_size;}
};

Class completement stupide, faite en 2 minutes, wrapper de base pour les tableaux C style.

Interface style vector histoire de dire qu'on peux securiser les acces avec at(), et grouper la taille avec size();

Array fait donc 8 octets, std::vector en fait 16.

Donc on gagne les 8 octets, et c'est exactement aussi lisible et autant securisé qu'un vector.

La seule difference c'est qu'on ne peut pas faire de push_back et autres joyeuseutés du vector, mais d'un autre coté, c'est un tableau d'une taille definie, donc c'est normal.

**azamharir** · 25/11/2007, 20h48

merci à tous,
Pour les problèmes de mémoires, c’est sur que je vais les avoir si je ne passe pas par disque aussi. Donc, je réfléchis maintenant sur une structure qui me facilitera ce passage. Pour les algorithmes : c’est voronoi dragram et network voronoi diagram avec stockage des résultats.
Merci encore.

**loufoque** · 26/11/2007, 01h59

Kujara, tes constructeurs de recopie et ton opérateur d'assignement ne sont pas valides. Ton code n'est pas non plus const-correct.
À part ça, bien sûr qu'on peut faire plus léger que std::vector, mais dans ce cas-là, tu ne peux pas agrandir le vecteur.
À noter que stocker la taille ne sert à rien non plus.

Ici en plus t'utilises forcément new[]/delete[], ce qui en fait un outil pas très utile pour les gens qui aiment affiner la gestion mémoire, et tous tes éléments sont forcément défaut construits à la construction de ton objet (ce qui signifie que peut pas y mettre grand chose de non trivial).

**CedricMocquillon** · 26/11/2007, 15h16

Salut

Je pense effectivement que savoir s'il faut utiliser un vector ou un tableau est peut-être un peu prématuré vu qu'il n'a pas déjà choisi la représentation de son graphe. Dans tout les cas, il vaut mieux pour lui utiliser des vecteurs et si après développement et optimisation des données stockées aux noeuds et sur les arcs, il a encore besoin de mémoire, il pourra utiliser sa propre classe optimisée en fonction de ses besoins. Pour ce qui est des algos j'avais vu des topics sur la partie algo du forum.

**NiamorH** · 27/11/2007, 14h37

Envoyé par Kujara

D'autant plus que c'est tout aussi facile de sortir d'un vector que de sortir d'un tableau, puisque l'operateur [] ne verifie pas les index...
Et oui, at() ça existe, mais apparemment 1) c'est pas assez connu 2) c'est plus lent.

Salut, je discutais avec quelqu'un qui m'a dit que at() vérifiait bien les index mais que rien n'était précisé pour l'operateur [] et que d'une implémentation à l'autre il pouvait y avoir le test. Ect-ce vrai ou pas ?

**yan** · 27/11/2007, 14h46

Envoyé par NiamorH

Salut, je discutais avec quelqu'un qui m'a dit que at() vérifiait bien les index mais que rien n'était précisé pour l'operateur [] et que d'une implémentation à l'autre il pouvait y avoir le test. Ect-ce vrai ou pas ?

oui. Pour l'operateur [], il n'y as pas de test sous GCC et il y as un (que l'on peut enlever) sous visual. Cela as déja été traité sur le forum.

Idée sur un graphe

C++

Discussions similaires

Partager

Partager