Disons que l'on me donne le chemin le plus court du nœud A au nœud B. Le chemin est simplement une liste d'arêtes, donc un chemin A-> B-> C, sera représenté par [(A, B), (B, C)].
Actuellement, chaque nœud est de type chaîne , un chemin d'un nœud à un autre, disons (A, B), est un ensemble de chaîne, et le chemin est une liste d'ensembles.
À présent, le chemin comprend plus de 60 000 arêtes et doit être enregistré dans une base de données pour une récupération ultérieure.
Alors évidemment, j'ai besoin d'une très belle façon de représenter ce chemin en C ++ de telle sorte que:
Quelqu'un peut-il me donner un aperçu?
Merci.
4 Réponses :
Il est difficile de voir exactement ce que vous voulez, mais peut-être que vous stockez simplement votre chemin comme:
std::map<int, std::string> route; // int is how many edges you've already travelled (starting from 0 for the first node) and the string is the node letter you're at by that point.
Cela vous donne une itération ordonnée de votre itinéraire et une efficacité décente pour les opérations sur la carte ( les opérations de recherche, de suppression et d'insertion ont une complexité logarithmique).
Pourquoi voulez-vous représenter des arêtes? Stockez des chemins entiers dans la base de données. Et n'hésitez pas à les stocker sous forme de chaînes (comme @vahancho l'a mentionné, utilisez ABCD au lieu de ABBCCD ). Il est évident que les arêtes appartiennent à ce chemin lorsque vous le regardez. Et vous pouvez même utiliser des caractères génériques plus tard pour rechercher, quels chemins contiennent une arête comme BC en utilisant % BC% dans les bases de données relationnelles.
L'efficacité de la mémoire dépend de la façon dont vous pouvez représenter vos données ( chemin ), si l'exemple que vous avez fourni est le cas, peut essayer M. suggestion vahancho .
Vous pouvez utiliser std :: unordered_map c'est juste pour la complexité de la mémoire et du temps , ou il serait peut-être préférable d'essayer de créer le vôtre structure de données pour stocker uniquement les informations utiles , hachage de votre chaîne de chemin, ... etc, peut en enveloppant SLT et surcharger certaines fonctionnalités.
Dans le cas d'une chaîne comme celle que vous fournissez ABBCCD , vous pouvez au lieu de stocker tous les chemins sous forme de chaînes, vous pouvez essayer de les stocker sous g-trie structure de données de cette manière, vous allez réduire la redondance sur le graphique de manière significative en tant que ABB et < code> AB chemins, qui vont être stockés sous forme de trois nœuds de char (1 octet ), l'idée est d'ignorer la sous-structure commune tel ( AB ).
Vous pouvez consulter cet article aussi.
Si vous copiez beaucoup les chaînes dans le code c ++ et qu'elles sont très volumineuses, vous pouvez envisager d'utiliser un pointeur ou un pointeur intelligent à la place. Il y a aussi la possibilité de hacher les chaînes, mais cela sera surtout utile pour les comparaisons. En général, pourquoi s'inquiéter d'utiliser des chaînes en premier lieu, sauf si elles sont très volumineuses comme des documents texte.
En ce qui concerne le conteneur, vous pouvez simplement utiliser un std::vector
Le moyen le plus efficace de stocker le chemin le plus court de A à B à la fin consiste simplement à stocker les points d'extrémité, puis à ne calculer le résultat que lorsque cela est nécessaire.
Vous utilisez les mêmes nœuds deux fois dans le chemin. Ne pouvez-vous pas représenter le chemin comme un
ABCDau lieu deABBCCD? Vous gagnerez de la mémoire.