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

https://stackoverflow.com/questions/1171

08-06-2019
|

Question

Je dois être capable de manipuler un grand graphique (10 ^ 7 nœuds) en python.Les données correspondant à chaque nœud/bord sont minimes, par exemple un petit nombre de chaînes.Quel est le plus efficace, en termes de mémoire et vitesse, comment faire ça ?

Un dicté de dictés est plus flexible et plus simple à mettre en œuvre, mais je m'attends intuitivement à ce qu'une liste de listes soit plus rapide.L'option list nécessiterait également que je garde les données séparées de la structure, tandis que les dicts 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 le pense en termes de récupération par 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 consiste à 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 d'un cas similaire qu'il pourrait partager.Après tout, les graphiques sont l’une des abstractions les plus courantes en CS.

La solution

Je vous conseille fortement de regarder RéseauX.Il s'agit d'un cheval de bataille éprouvé et du premier outil auquel la plupart des types de « recherche » se tournent lorsqu'ils ont besoin d'analyser des données basées sur un réseau.J'ai manipulé des graphiques avec des centaines de milliers d'arêtes sans problème sur un ordinateur portable.Ses fonctionnalités sont riches et très simples à utiliser.Vous vous concentrerez davantage sur le problème en question plutôt que sur les détails de la mise en œuvre sous-jacente.

Exemple de Erdős-Rényi génération et analyse de graphiques aléatoires


"""
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 également simples :

enter image description here

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

Autres conseils

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.Il 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 Boost Graph.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 bien meilleures que le code Python typique, sans sacrifier la facilité d'utilisation.Je l'utilise moi-même constamment pour travailler avec de très grands graphiques.

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

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

À en juger par votre exemple, « Propriété », préféreriez-vous une approche de classe pour le niveau final et les propriétés immobilières ?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 (insertion, mise à jour, suppression)
vitesse de récupération par 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 offrir un accès relativement rapide et relativement uniforme. Il utilisera probablement plus de mémoire que, comme vous le suggérez, les listes.Cependant, les listes 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 simplement d'utiliser la méthode qui vous semble la plus naturelle, puis de faire un "test de résistance" 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, afin de ne pas avoir à modifier l'interface de programmation si vous devez ultérieurement modifier la structure de données interne.

Si je comprends bien, l'accès aléatoire se fait en temps constant pour les dictionnaires et les listes de Python, la différence est que vous ne pouvez effectuer 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 dicts.

Cependant, du point de vue des performances, le charger en mémoire n'est peut-être pas un problème, mais si vous en utilisez trop, vous finirez par passer au disque, ce qui tuera les performances même des dictés très efficaces de Python.Essayez de réduire autant que possible l’utilisation de la mémoire.De plus, la RAM est incroyablement bon marché à l’heure actuelle ;si vous faites souvent ce genre de chose, il n'y a aucune raison de ne pas avoir au moins 4 Go.

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

Créer une structure basée sur les classes entraînerait probablement plus de frais généraux que la structure basée sur des dicts, car dans Python, les classes utilisent en fait des dicts lorsqu'elles sont implémentées.

Il ne fait aucun doute que NetworkX est jusqu'à présent la meilleure structure de données pour les graphiques.Il est livré avec des utilitaires tels que des fonctions d'assistance, des structures de données et des algorithmes, des générateurs de séquences aléatoires, des décorateurs, la commande Cuthill-Mckee, des gestionnaires de contexte.

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

Il implémente divers algorithmes radimade, notamment :Approximation, bipartite, frontière, centralité, clique, clustering, coloration, composants, connectivité, cycles, graphiques acycliques dirigés, mesures de distance, ensembles dominants, eulérien, isomorphisme, analyse de liaison, prédiction des liens, apparie Chemins, traversée, arbre.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow