Quelle est la structure de données graphique la plus efficace en Python?

Question

J'ai besoin d'être capable de manipuler une grande (10^7 nœuds) graphique en python. Les données correspondant à chaque nœud/edge est minime, disons, un petit nombre de chaînes. Ce qui est le plus efficace, en termes de mémoire et de la vitesse, façon de le faire?

Un dict des dicts est plus souple et plus simple à mettre en œuvre, mais je intuitivement s'attendre à une liste de listes pour être plus rapide. La liste d'option exigerait aussi que je conserver les données distincte de la structure, tandis que les dicts permettrait de quelque chose de la sorte:

graphe[I][J]["Propriété"]="valeur"

Que suggérez-vous?

---

Oui, j'aurais été un peu plus clair sur ce que je veux dire par l'efficacité. Dans ce cas particulier, je veux dire en termes d'accès aléatoire de récupération.

Le chargement des données dans la mémoire n'est pas un énorme problème. C'est fait une fois pour toutes. Le temps de la partie est de visiter les nœuds de sorte que je peux extraire l'information et de mesurer les paramètres, je suis intéressé.

Je n'avais pas envisagé de faire chaque nœud une classe (propriétés sont les mêmes pour tous les nœuds), mais il semble que ce serait ajouter une couche supplémentaire de frais généraux? J'espérais que quelqu'un aurait une certaine expérience en direct avec un cas similaire qu'ils pourraient partager. Après tout, les graphiques sont l'un des plus commune des abstractions dans CS.

Answer 1

Je vous recommande fortement de vous regarder NetworkX. C'est un des combats de la guerre de cheval et le premier outil le plus de la "recherche" types atteindre pour quand ils en ont besoin pour faire de l'analyse de réseau en fonction des données. J'ai manipulé des graphiques avec 100s de milliers de bords sans problème sur un portable. Son riche en fonctionnalités et très facile à utiliser. Vous vous trouverez en plus l'accent sur le problème à la main plutôt que sur les détails de l'implémentation sous-jacente.

Exemple d' Erdős-Rényi aléatoire graphique de génération et d'analyse

"""
Create an G{n,m} random graph with n nodes and m edges
and report some properties.

This graph is sometimes called the Erd##[m~Qs-Rényi graph
but is different from G{n,p} or binomial_graph which is also
sometimes called the Erd##[m~Qs-Rényi graph.
"""
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
__credits__ = """"""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg 
#    Dan Schult 
#    Pieter Swart 
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html

from networkx import *
import sys

n=10 # 10 nodes
m=20 # 20 edges

G=gnm_random_graph(n,m)

# some properties
print "node degree clustering"
for v in nodes(G):
    print v,degree(G,v),clustering(G,v)

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout)

Les visualisations sont aussi simple:

Plus de visualisation: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Answer 2

Même si cette question est maintenant assez vieux, je pense qu'il vaut la peine de mentionner mon propre module python pour graphique de manipulation que l'on appelle graphe de l'outil. Il est très efficace, puisque les structures de données et algorithmes sont implémentés en C++, avec le modèle metaprograming, en utilisant le Boost Graph Library. Donc ses performances (à la fois dans l'utilisation de la mémoire et de l'exécution) est comparable à un pur C++ de la bibliothèque, et peut-être des ordres de grandeur supérieures à typique du code python, sans sacrifier la facilité d'utilisation. J'utilise moi-même constamment de travailler avec de très grands graphes.

Answer 3

Comme déjà mentionné, NetworkX est très bon, avec une autre option étant igraph . Les deux modules auront la plupart (sinon la totalité) des outils d'analyse dont vous aurez probablement besoin, et les deux bibliothèques sont utilisées de manière routinière avec les grands réseaux.

Answer 4

Un dictionnaire peut également contenir des frais généraux, en fonction de la réelle mise en œuvre. Une table de hachage contient habituellement quelques le premier nombre de nœuds disponibles pour commencer, même si vous pouvez seulement utiliser un couple de nœuds.

À en juger par votre exemple, "Propriété", vous serait mieux avec une approche de classe pour le niveau final et biens immobiliers? Ou est la liste des noms des propriétés de changer beaucoup de nœud à nœud?

Je dirais que ce "efficace" signifie dépend de beaucoup de choses, comme:

• la vitesse des mises à jour (insert, update, delete)
• la vitesse de l'accès aléatoire de récupération
• la vitesse de la recherche séquentielle
• mémoire utilisée

Je pense que vous verrez que d'une structure de données qui est rapide généralement consomment plus de mémoire que celle qui est lent. Ce n'est pas toujours le cas, mais la plupart des structures de données semble suivre cette.

Un dictionnaire peut être facile à utiliser, et vous donner relativement uniformément rapide d'accès, il sera très probablement utiliser plus de mémoire que, comme vous le suggérez, les listes. Listes, cependant, en général, ont tendance à contenir plus de charge lorsque vous insérez des données dans elle, à moins qu'ils préallouer les nœuds X, dans lequel ils seront à nouveau utiliser plus de mémoire.

Ma suggestion, en général, est d'utiliser la méthode qui lui semble la plus naturelle pour vous, et puis faire un "stress test" du système, l'ajout d'une quantité importante de données et voir si cela devient un problème.

Vous pourriez aussi envisager d'ajouter une couche d'abstraction pour votre système, de sorte que vous n'avez pas à changer l'interface de programmation si vous plus tard sur la nécessité de modifier la structure de données interne.

Answer 5

Ce que je comprends, l'accès aléatoire est en temps constant pour les deux Python dicts et des listes, la différence est que vous ne pouvez le faire à accès aléatoire de l'index entiers avec des listes. Je suis en supposant que vous avez besoin à la recherche d'un nœud par son étiquette, si vous voulez un dict des dicts.

Cependant, au niveau de la performance, de le charger en mémoire peut ne pas être un problème, mais si vous les utilisez trop, vous finirez échange sur le disque, qui va tuer la performance, même en Python est très efficace dicts. Essayez de garder l'utilisation de la mémoire vers le bas autant que possible. Aussi, la RAM est étonnamment bon marché dès maintenant; si vous faites ce genre de chose beaucoup, il n'y a aucune raison de ne pas avoir au moins 4 GO.

Si vous souhaitez obtenir des conseils sur le maintien de l'utilisation de la mémoire, donner plus d'information sur le type d'informations que vous avez suivi pour chaque nœud.