J'utilise adjacency_list Étant donné que mes graphiques sont statiques après le chargement et le compte de bord et de sommet
sont connus à l'avance, je vois un énorme potentiel d'optimisation. Pour
Exemple, j'aimerais affecter un seul tampon pour tous les sommets / bords
d'un graphe unique et laissez le graphique stocker simplement des indices dans ce tampon. Plus de questions: Est-ce que quelqu'un a déjà construit une version BGL optimisée pour une utilisation de la mémoire?
Devrais-je essayer d'utiliser les structures de graphique existantes et l'augmenter avec
allocators personnalisés ou somesuch ou est-il plus fructueux d'écrire mon propre
implémentation et essayer de rester à l'interface compatible avec la BGL afin
Je peux continuer à utiliser ses algorithmes? meilleures salutations,
1) Quelle est la mémoire de mémoire d'utiliser des propriétés Vertex et Edge? je
en avez assez quelques-uns.
2) Est-il possible de convaincre la BGL d'utiliser le rétrécissement pour s'adapter
idiome? Si je comprends bien, les listes d'adjacence utilisent Push_back pour ajouter
bords. Est-il possible de réduire l'utilisation de la mémoire en échangeant le
Vecteur résultant avec une copie d'elle-même? Peut-être en copiant le tout
graphique?
3) Est-il possible d'utiliser des allocateurs de piscine boost avec la BGL? Aussi loin
Comme je peux dire que la BGL effectue actuellement beaucoup de petites allocations -
J'aimerais vraiment éviter cela pour des raisons d'efficacité de l'espace et de l'exécution.
4 Réponses :
Etant donné que BGL est conçu pour Interopérer avec héritage ou Graphes personnalisés , vous êtes probablement le meilleur de votre propre graphique.
La surcharge dépend de la version que vous utilisez et si vous êtes allé pour des propriétés "groupées" ou non. Je n'ai utilisé que des propriétés groupées et la lecture du code que je m'attendais à ce que chaque paquet de propriétés coûte 2 pointeurs + taille du type de paquet que vous utilisez + taille de chacune des propriétés connectées. Aucun des trucs de concept de vérification n'est laissé dans l'Afaik binaire. Depuis que vous avez le code, pourquoi ne pas simplement mesurer le coût? Si vous n'avez pas d'outillage pour aider à essayer de générer des graphiques de tailles connues dans des tampons de tailles connues. Quelque chose échouera finalement et à ce moment-là, vous devriez avoir des comptes.
Avez-vous essayé appeler ???
J'ai commencé à écrire quelque chose comme le système que vous décrivez, mais éventuellement abandonné sur la BGL et éventuellement modifié pour coder mes propres algorithmes pour exécuter une base de données SQLITE de tous les symboles de liaison. adjacency_list
Oui, j'ai essayé de rétrécir (Suggestion n ° 2), mais cela n'a pas beaucoup aidé. Nous utilisons également des backens de base de données et prennent en charge actuellement MySQL, PostgreSQL et SQLite. Cependant, nos schémas d'accès pour ces algorithmes particuliers nécessitent réellement une structure de données spécialisée en mémoire.
Il y a un type de graphique peu connu appelé graphique "Compressé Spears Row" dans la BGL. Il semble être assez nouveau et n'est pas lié à partir des pages d'index. Il emploie cependant une belle petite astuce pour obtenir la représentation graphique aussi petite que possible. http://www.boost.org/doc/libs /1_40_0/libs/graph/doc/compressed_sparse_row.html
Utiliser ceci pour certains de nos graphiques, j'ai déjà été en mesure de réduire l'utilisation totale de la mémoire de 20% - il s'agit donc d'une optimisation très intéressante.
Il stocke également les propriétés de Vertex / Edge dans les vecteurs, donnant ainsi les plus petits frais généraux possibles pour ceux-ci.
Notez que la version expédition avec le dernier boost 1.40 prend en charge des graphiques directionnels uniquement (par opposition à la bidirectionnelle). Si vous devez être capable de parcourir efficacement les sorties et les bords de Vertice (comme je l'ai fait), vous devez vérifier le coffre de boost de Subversion. Jérémie était très utile pour ajouter cette fonctionnalité sur ma demande.
comme une réponse à:
3) est-il possible d'utiliser des allocateurs de piscine boost avec la BGL? Pour autant que possible de dire que la BGL effectue actuellement beaucoup de petites allocations - j'aimerais vraiment éviter cela pour des raisons d'efficacité de l'espace et de l'exécution. P> blockQquote>
code copié de ici : P >
template <class Allocator> struct list_with_allocatorS { }; namespace boost { template <class Alloc, class ValueType> struct container_gen<list_with_allocatorS<Alloc>, ValueType> { typedef typename Alloc::template rebind<ValueType>::other Allocator; typedef std::list<ValueType, Allocator> type; }; } // now you can define a graph using std::list // and a specific allocator typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;
Ce n'est peut-être pas la réponse que vous aimez, mais en ce qui concerne l'octet-comptant comme une préparation à un piratage dans une bibliothèque de Boost, qui n'est utilisée que pour très peu de tâches - vous obtiendrez une meilleure réponse plus tôt dans la liste de diffusion utilisateur de Boost < lists.boost.org/mailman/listinfo.cgi/boost-UserSers>. Autre possibilité est de lire la source ...