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

Translate

J'ai besoin de pouvoir manipuler un grand graphe (10 ^ 7 nœuds) en python. Les données correspondant à chaque nœud / bord sont minimes, disons un petit nombre de chaînes. Quel est le plus efficace, en termes demémoire et vitesse, façon de faire ça?

Un dict of dicts est plus flexible et plus simple à implémenter, mais je m'attends intuitivement à ce qu'une liste de listes soit plus rapide. L'option de liste exigerait également que je garde les données séparées de la structure, tandis que les dictionnaires permettraient quelque chose du genre:

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

Que suggérerais-tu?


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

Le chargement des données en mémoire n'est pas un gros problème. C'est fait une fois pour toutes. La partie qui prend du temps est de visiter les nœuds afin que je puisse extraire les informations et mesurer les métriques qui m'intéressent.

Je n'avais pas envisagé de faire de chaque nœud une classe (les propriétés sont les mêmes pour tous les nœuds) mais il semble que cela ajouterait une couche supplémentaire de surcharge? J'espérais que quelqu'un aurait une expérience directe avec un cas similaire qu'il pourrait partager. Après tout, les graphiques sont l'une des abstractions les plus courantes dans CS.

This question and all comments follow the "Attribution Required."

Toutes les réponses

Translate

Je vous recommande fortement de regarderNetworkX. C'est un cheval de bataille éprouvé et le premier outil utilisé par la plupart des types de «recherche» lorsqu'ils ont besoin d'analyser des données basées sur le réseau. J'ai manipulé des graphiques avec des centaines de milliers d'arêtes sans problème sur un ordinateur portable. Sa fonctionnalité est riche et très facile à utiliser. Vous vous concentrerez davantage sur le problème à résoudre que sur les détails de la mise en œuvre sous-jacente.

Exemple deErdős-Rényigénération et analyse aléatoires de graphes


"""
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 ([email protected])"""
__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 également simples:

enter image description here

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

La source
Translate

Même si cette question est maintenant assez ancienne, je pense qu'il vaut la peine de mentionner mon propre module python pour la manipulation de graphes appeléoutil graphique. C'est très efficace, puisque les structures de données et les algorithmes sont implémentés en C ++, avec une métaprogrammation de modèles, en utilisant la bibliothèque de graphes Boost. Par conséquent, ses performances (à la fois en termes d'utilisation de la mémoire et d'exécution) sont comparables à celles d'une bibliothèque C ++ pure, et peuvent être d'un ordre de grandeur meilleures que le code python typique, sans sacrifier la facilité d'utilisation. Je l'utilise moi-même en permanence pour travailler avec de très gros graphiques.

La source
Kai
Translate

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

La source
Translate

Un dictionnaire peut également contenir une surcharge, en fonction de l'implémentation réelle. Une table de hachage contient généralement un nombre premier de nœuds disponibles pour commencer, même si vous n'utilisez que quelques nœuds.

À en juger par votre exemple, «Propriété», seriez-vous mieux avec une approche de classe pour le niveau final et les propriétés réelles? Ou les noms des propriétés changent-ils beaucoup d'un nœud à l'autre?

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

  • vitesse des mises à jour (insérer, mettre à jour, supprimer)
  • 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 constaterez qu'une structure de données rapide consommera généralement plus de mémoire qu'une structure lente. Ce n'est pas toujours le cas, mais la plupart des structures de données semblent suivre cela.

Un dictionnaire peut être facile à utiliser et vous donner un accès relativement rapide, il utilisera probablement plus de mémoire que, comme vous le suggérez, les listes. Les listes, cependant, ont généralement tendance à contenir plus de surcharge lorsque vous y insérez des données, à moins qu'elles ne préallouent des nœuds X, dans lesquels elles utiliseront à nouveau plus de mémoire.

Ma suggestion, en général, serait d'utiliser simplement la méthode qui vous semble la plus naturelle, puis de faire un "stress test" du système, en y ajoutant une quantité substantielle de données et de voir si cela devient un problème.

Vous pouvez également envisager d'ajouter une couche d'abstraction à votre système, de sorte que vous n'ayez pas à changer l'interface de programmation si vous devez ultérieurement modifier la structure de données interne.

La source
Translate

Si je comprends bien, l'accès aléatoire est en temps constant pour les dictionnaires et les listes de Python, la différence est que vous ne pouvez faire qu'un accès aléatoire aux index entiers avec des listes. Je suppose que vous devez rechercher un nœud par son étiquette, vous voulez donc un dict de dictés.

Cependant, sur le plan des performances, le charger en mémoire peut ne pas être un problème, mais si vous en utilisez trop, vous finirez par échanger sur le disque, ce qui tuera les performances même des dictionnaires très efficaces de Python. Essayez de réduire autant que possible l'utilisation de la mémoire. En outre, la RAM est incroyablement bon marché en ce moment; si vous faites beaucoup ce genre de choses, il n'y a aucune raison de ne pas avoir au moins 4 Go.

Si vous souhaitez des conseils sur la réduction de l'utilisation de la mémoire, donnez plus d'informations sur le type d'informations que vous suivez pour chaque nœud.

La source
Translate

Créer une structure basée sur des classes aurait probablement plus de surcharge que la structure basée sur des dict, car en python, les classes utilisent en fait des dicts lorsqu'ils sont implémentés.

La source
Translate

Nul doute que NetworkX est la meilleure structure de données à ce jour pour le graphe. Il est livré avec des utilitaires tels que les fonctions d'assistance, les structures de données et les algorithmes, les générateurs de séquences aléatoires, les décorateurs, la commande Cuthill-Mckee, les gestionnaires de contexte

NetworkX est génial car il fonctionne pour les graphiques, les digraphes et les multigraphes. Il peut écrire des graphiques de plusieurs manières: liste d'adjacence, liste d'adjacence multiligne, liste des bords, GEXF, GML. Il fonctionne avec Pickle, GraphML, JSON, SparseGraph6 etc.

Il a implémenté divers algorithmes de radimade, notamment: approximation, bipartite, frontière, centralité, clique, clustering, coloration, composants, connectivité, cycles, graphes acycliques dirigés, mesures de distance, ensembles dominants, eulérien, isomorphisme, analyse de lien, prédiction de lien, correspondance , Arbre couvrant minimum, club riche, chemins les plus courts, traversée, arbre.

La source