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

voix
63

Je dois être capable de manipuler un grand (10 ^ 7 noeuds) graphique en python. Les données correspondant à chaque noeud / bord est minime, disons, un petit nombre de chaînes. Ce qui est le plus efficace, en termes de mémoire et de vitesse , façon de le faire?

Un dict de dicts est plus souple et plus simple à mettre en œuvre, mais je me attends intuitivement une liste de listes pour être plus rapide. L'option de la liste serait également exiger que je garde les données séparées de la structure, alors que dicts permettrait quelque chose du genre:

graph[I][J][Property]=value

Que suggérerais-tu?


Oui, je suis un peu plus clair sur ce que je veux dire par l'efficacité. Dans ce cas particulier, je veux dire en termes de recherche d'accès aléatoire.

Le chargement des données dans la mémoire n'est pas un énorme problème. Cela se fait une fois pour toutes. La partie chronophage visite les nœuds afin que je puisse en extraire les informations et mesurer les mesures qui me intéressent.

Je ne l'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 expérience directe avec un cas similaire qu'ils pourraient partager. Après tout, les graphiques sont l'une des abstractions les plus courantes dans CS.

Créé 04/08/2008 à 13:00
source utilisateur
Dans d'autres langues...                            


7 réponses

voix
51

Je fortement plaider en faveur que vous regardez NetworkX . Il est un cheval de guerre bataille testé et le premier outil « la plupart des types de recherche » atteignent quand ils ont besoin pour faire l' analyse des données basées sur le réseau. Je l' ai manipulé graphiques avec 100s de milliers d'arêtes sans problème sur un ordinateur portable. Sa caractéristique riche et très facile à utiliser. Vous vous trouverez se concentrant davantage sur le problème à la main plutôt que les détails dans la mise en œuvre sous - jacente.

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


"""
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)

Visualisations sont aussi simples:

entrez la description d'image ici

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

Créé 26/08/2008 à 18:43
source utilisateur

voix
12

Même si cette question est maintenant assez vieux, je pense qu'il vaut la peine de mentionner mon propre module python pour la manipulation graphique appelé graphique-outil . Il est très efficace, car les structures de données et algorithmes sont implémentés en C ++, avec le modèle méta - programmation, en utilisant le Boost Graph Library. Par conséquent , ses performances (aussi bien dans l' utilisation de la mémoire et l' exécution) est comparable à une bibliothèque C ++ pur, et peut être des ordres de grandeur mieux que le code Python typique, sans pour autant sacrifier la facilité d'utilisation. Je l' utilise moi - même constamment travailler avec des graphiques très grandes.

Créé 27/11/2010 à 15:10
source utilisateur

voix
6

Comme déjà mentionné, NetworkX est très bon, avec une autre option étant igraph . Les deux modules auront la plupart (sinon tous) les outils d'analyse que vous êtes susceptibles d'avoir besoin, et les deux bibliothèques sont couramment utilisés avec de grands réseaux.

Créé 27/08/2008 à 11:01
source utilisateur

voix
4

Un dictionnaire peut également contenir les frais généraux, en fonction de la mise en œuvre effective. Une table de hachage contiennent généralement un nombre premier de noeuds disponibles pour commencer, même si vous pouvez utiliser seulement quelques nœuds.

A en juger par votre exemple, « la propriété », seriez-vous mieux avec une approche de classe pour le niveau final et les propriétés réelles? Ou est le nom des propriétés changeant beaucoup de noeud à noeud?

Je dirais que ce moyen « efficace » dépend de beaucoup de choses, comme:

  • la vitesse des mises à jour (insertion, mise à jour, suppression)
  • vitesse de récupération d'accès aléatoire
  • vitesse de récupération séquentielle
  • mémoire utilisée

Je pense que vous trouverez qu'une structure de données est rapide consommera généralement 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 cela.

Un dictionnaire peut être facile à utiliser, et vous donner un accès rapide relativement uniforme, il sera très probablement utiliser plus de mémoire que, comme vous le suggérez, listes. Les listes, cependant, ont généralement tendance à contenir plus de frais généraux lorsque vous insérez des données dans, à moins qu'ils Préallouer nœuds X, dans lequel ils utiliseront encore plus de mémoire.

Ma suggestion, en général, serait de simplement utiliser la méthode qui vous semble le plus naturel, 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 pouvez également envisager d'ajouter une couche d'abstraction à votre système, de sorte que vous ne devez pas changer l'interface de programmation si vous plus tard besoin de changer la structure de données interne.

Créé 04/08/2008 à 13:09
source utilisateur

voix
3

Si je comprends bien, l'accès aléatoire est en constante de temps pour les dicts de Python et des listes, la différence est que vous ne pouvez pas accès aléatoire des indices entiers avec des listes. Je suppose que vous avez besoin de rechercher un noeud par son étiquette, si vous voulez un dict de dicts.

Cependant, sur le plan de la performance, le chargement dans la mémoire ne peut pas être un problème, mais si vous utilisez trop, vous finirez par échange sur le disque, ce qui va tuer les performances de même dicts très efficaces de Python. Essayez de garder l'utilisation de la mémoire vers le bas autant que possible. En outre, la RAM est étonnamment pas cher en ce moment; 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 des conseils sur le maintien de bas utilisation de la mémoire, donner plus d'informations sur le type d'information que vous suivi pour chaque noeud.

Créé 06/08/2008 à 06:37
source utilisateur

voix
2

Faire une structure à base de classe aurait probablement plus de frais généraux que la structure à base dict, puisque dans les classes Python utilisent effectivement dicts quand ils sont mis en œuvre.

Créé 04/08/2008 à 13:41
source utilisateur

voix
1

Sans doute NetworkX est la meilleure structure de données jusqu'à présent pour le graphique. Il est livré avec des utilitaires comme fonctions d'assistance, structures de données et algorithmes, générateurs de séquence aléatoire, décorateurs, commande Cuthill-Mckee, gestionnaires de contexte

NetworkX est grand parce qu'il wowrs pour les graphiques, digraphs et multigraphes. Il peut écrire graphique avec de multiples façons: Liste contiguïté, multiligne contiguïté Liste, Liste Edge, GEXF, GML. Il fonctionne avec Pickle, graphml, JSON, etc. SparseGraph6

Il a implimentation de divers algorithmes radimade dont: Approximation, bipartites, Limite, centralité, Clique, Clustering, coloriage, Composants, connectivité, Cycles, acyclique orienté graphiques, mesures de distance, ensemble dominant, Eulerian, Isomorphisme, Analyse des liens, la prévision du lien, assorti , minimum Spanning Tree, Rich club, les plus courts chemins, Traversal, Arbre.

Créé 18/01/2016 à 09:08
source utilisateur

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more