Bonjour, je cherche à faire un graphe qui stocke des noeuds. Les noeuds sont très simple il s’agit juste d’entiers de type uint32, donc il y a le noeud 1, 2, etc. Je veux la solution la plus performante en mémoire et en temps pour stocker le graphe, c’est à dire les liens entre les noeuds.
J’avais pensé utiliser un std::vector<std::vector<uint32_t>> qui stockerait à l’indice i les noeuds fils du noeud i. Le problème est que ça me parait pas très efficace car il va y avoir des allocations que je veux éviter. Je veux qu’il y ait qu’une seule allocation pour tout le graphe si possible.
J’avais pensé à faire une matrice d’adjacence mais ça va consommer trop de mémoire. Du coup comment faire ? Y a t il une meilleure représentation que le vecteur de vecteur ? La taille n’est pas connue à la compilation et peut être très grande donc les tableaux statiques c’est pas possible.
Je pense que pour donner la "meilleure façon", il faut savoir ce que tu comptes faire des données qui y seront stockées. Pourquoi les stocker dans un graphe ? Peut-être des conteneurs standard font déjà l'affaire.
Je sais pas ce que je veux faire avec, c’est pour implémenter différents algorithmes de parcours de graphe etc
Quels algorithmes ?
Sous quelle forme sont donnés les graphes au départ ?
Leur taille, quel ordre de grandeur ?
> ce ça me parait pas très efficace car il va y avoir des allocations que je veux éviter.
Qu'est ce qui te fait dire que ça ne sera pas efficace ? A combien tu estimes le temps de "chargement" du graphe par rapport au temps d'exécution de tes algorithmes ? Quelle importance ?
- Edité par michelbillaud 24 avril 2023 à 12:43:05
Dans un vecteur de vecteurs, ce n'est pas nécessaire que tous les "sous-vecteurs" aient la même longueur.
Pourrais-tu nous mentionner quels algorithmes de parcours tu penses écrire.?
Oui tous les sous vecteurs peuvent avoir des tailles différentes. J'ai envie de faire des algorithmes classiques de parcours en profondeur, largeur et des recherches de plus court chemin.
Fvirtman a écrit:
- soit tu veux stocker un graphe et permettre l'ajout de nouveaux noeuds et arètes.
- soit tu veux stocker un graphe "fini", tu n'ajoutes plus rien, tes algos derrière ne font que lire le graphe.
En soi je veux exécuter des algos sur un graphe fini, mais le temps de le construire il est pas fini du coup.
michelbillaud a écrit:
MahometUrsufa a écrit:
Je sais pas ce que je veux faire avec, c’est pour implémenter différents algorithmes de parcours de graphe etc
Quels algorithmes ?
Sous quelle forme sont donnés les graphes au départ ?
Leur taille, quel ordre de grandeur ?
> ce ça me parait pas très efficace car il va y avoir des allocations que je veux éviter.
Qu'est ce qui te fait dire que ça ne sera pas efficace ? A combien tu estimes le temps de "chargement" du graphe par rapport au temps d'exécution de tes algorithmes ? Quelle importance ?
Les graphes que je veux sont juste des noeuds numérotés reliés entre eux. Quand je dis que c'est pas efficace je veux pas dire que ça sera lent, car ça sera pas le cas tout se fera instantanément, c'est juste que j'ai envie de trouver un moyen de faire tourner le truc le plus efficacement possible, mais ça sert à rien en soi.
J'avais pensé sinon peut être à utiliser des std::pmr::vector avec un std::pmr::monotonic_buffer_resource, j'ai vu cette vidéo qui en parle apparemment c'est rapide https://www.youtube.com/watch?v=q6A7cKFXjY0
> J'ai envie de faire des algorithmes classiques de parcours en profondeur, largeur et des recherches de plus court chemin. Algorithme de parcours en profondeur: ça te prend la liste des noeuds (ou arcs) sortants de chaque noeud. En plus probablement une liste des noeuds rencontrés. Comment sauras-tu si tu boucles? Algorithme de parcours en largeur: ça te prend en plus une file (std::dequeue?). Plus court chemin: plus d'un algo; avec Dijkstra, ça te prend une file de priorité. En plus, si tu décides d'associer un poids à chaque arc, où le mettras-tu? Sauras-tu faire tout cela? Est-ce que tes graphes seront orientés ou pas? > En soi je veux exécuter des algos sur un graphe fini, mais le temps de le construire il est pas fini du coup. Pourquoi? Tu ne comprends pas comment faire? Comment se présentent tes données? Des paires de noeud? Dans d'autres langages j'aurais utilisé des dictionnaires de dictionnaires. Pourquoi pas des map de map?
Si les numéros de sommet sont consécutifs et le maximum connu, des vecteurs de vecteurs de structures (ou de tuples / paires) peuvent suffire.
- Edité par PierrotLeFou 25 avril 2023 à 2:03:37
Le Tout est souvent plus grand que la somme de ses parties.
Il y a déjà une chose intéressante à savoir au sujet des réallocations de std::vector : elles sont faites de manière à doubler (ou presque) la capacité totale du tableau à chaque fois.
Cela implique que plus tu auras d'éléments à ajouter, moins les réallocations nécessaires prendront du temps en proportion.
Comme tu peux le voir, j'ajoute jusqu'à 8 500 000 valeurs à partir d'un tableau vide, et il n'y a pourtant que 25 réallocations effectuées. Plus intéressant encore, les dix premières surviennent avant d'avoir atteint les 512 éléments.
De plus, il existe deux fonctions géniale de std::vector qui te permettent d'éviter bon nombre de réallocation si tu arrive à estimer (ne serait-ce que plus ou moins) le nombre d'éléments qu'ils vont contenir:
la fonction reserve qui augmente la capacité du tableau (au travers d'une réallocation de la mémoire) sans augmenter le nombre d'éléments "actuel" du tableau, et qui implique donc que chaque ajout devra se faire avec push_back et autres
la fonction resize qui permet de définir une nouvelle taille de tableau en générant des éléments "par défaut" pour les éléments ajoutés et qui implique que tous les éléments soient accessibles directement au travers des opérateurs d'indice []
Et je ne te parle même pas des constructeurs de std::vector dont certains permettent de définir directement le nombre d'éléments qu'ils doivent s'attendre à contenir...
Si donc, tu es en mesure d'esitmer "plus ou moins précisément" le nombre d'élément que contiennent (ou contiendront) tes tableaux, tu dois pouvoir réduire le besoin de réallocations de mémoire au stricte minimum en faisant en sorte qu'elles soient effectuées "une bonne fois pour toutes".
Tout cela pour dire que ton principal problème ne risque très clairement pas d'être la réallocation de mémoire lors du remplissage de ton std::vector, mais que le véritable problème sera plutôt celui de la contiguité des éléments en mémoire car c'est ce dernier point qui rendra la représentation de ton graphe "cache friendly" ou non (comprend: que le processeur sera en mesure d'éviter au maximum les "cache miss" lors de l'accès au données ).
Mais là, je dois partir travailler, alors qu'il y a encore pas mal de points à prendre en compte ... La suite au prochain épisode
- Edité par koala01 25 avril 2023 à 7:35:19
Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait
Le mieux que tu puisses faire, c'est de commencer à écrire une première version de ton programme, sans trop t'occuper d'efficacité à priori. Choisis un algorithme (*), et écris le code.
Quand ca sera fait, tu pourras étudier les performances, avec des chiffres mesurés , plutôt que d'en parler dans le vague. Au besoin, tu écriras d'autres versions avec des représentations différentes, et tu pourras comparer cette fameuse efficacité.
Ça te fera plusieurs exercices pour le même prix.
(*) il n'y a pas de "meilleure façon" qui conviendrait idéalement à tous les algorithmes sur les graphes.
- Edité par michelbillaud 25 avril 2023 à 8:30:22
Meilleure façon de stocker un graphe ?
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Le Tout est souvent plus grand que la somme de ses parties.