Domanda

Ho bisogno di essere in grado di manipolare un grande (10^7 nodi) il grafico in python.I dati corrispondenti per ogni nodo/edge è minima, diciamo, un piccolo numero di stringhe.Che cosa è il più efficiente, in termini di la memoria e la velocità, come posso fare?

Un dict di dicts è più flessibile e più semplice da implementare, ma io intuitivamente si aspettano un elenco di elenchi per essere più veloce.Elenco opzione richiede inoltre che I tenere i dati separati dalla struttura, mentre dicts consentirebbe qualcosa del genere:

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

Cosa suggeriresti?


Sì, avrei dovuto essere un po ' più chiaro che cosa si intende per efficienza.In questo caso particolare, intendo in termini di accesso casuale di recupero.

Il caricamento dei dati nella memoria non è un problema enorme.Fatto questo una volta per tutte.La parte che richiede tempo, è in visita i nodi in modo che posso estrarre le informazioni e misurare le metriche che mi interessa.

Io avevo pensato di fare ogni nodo di una classe (le proprietà sono le stesse per tutti i nodi), ma mi sembra che aggiungere un ulteriore livello di sovraccarico?Speravo che qualcuno avesse qualche esperienza diretta con un caso simile che hanno potuto condividere.Dopo tutto, i grafici sono uno dei più comuni astrazioni in CS.

È stato utile?

Soluzione

Vorrei fortemente avvocato si guarda NetworkX.E ' una battaglia-testato cavallo di guerra e il primo strumento piu 'ricerca' tipi di raggiungere per quando hanno bisogno di fare analisi di rete di base di dati.Ho manipolato i grafici con 100s di migliaia di bordi senza problema su un notebook.Il suo ricco di funzionalità e facile da usare.Vi troverete di messa a fuoco più sul problema a portata di mano, piuttosto che i dettagli nell'implementazione sottostante.

Esempio di Erdős-Rényi casuale di generazione di grafici e analisi


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

Le visualizzazioni sono anche semplice:

enter image description here

Più di visualizzazione: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Altri suggerimenti

Anche se questa domanda è ora abbastanza vecchio, penso che vale la pena di citare il mio proprio modulo python per grafico manipolazione chiamata grafico-strumento.È molto efficiente, in quanto le strutture di dati e algoritmi implementati in C++, con modello metaprograming, usando il Boost Grafico Libreria.Pertanto le sue prestazioni (sia in memoria di utilizzo e runtime) è paragonabile a un puro C++ library, e può essere ordini di grandezza rispetto ai tipici del codice python, senza sacrificare la facilità d'uso.Io lo uso io stesso costantemente al lavoro con i grafici di grandi dimensioni.

Come già accennato, NetworkX è molto buona, con un'altra opzione igraph.Entrambi i moduli hanno la maggior parte (se non tutti) gli strumenti di analisi è molto probabile che bisogno, e entrambe le librerie sono abitualmente utilizzati con reti di grandi dimensioni.

Un dizionario può contenere anche l'overhead, in funzione dell'effettiva attuazione.Una tabella hash di solito contengono alcuni primo numero di nodi disponibili per cominciare, anche se si potrebbe usare solo un paio di nodi.

A giudicare dal tuo esempio, "Proprietà", sarebbe meglio con un approccio classe per il livello finale e immobili?O i nomi delle proprietà cambiando molto da nodo a nodo?

Direi che la cosa "efficiente" significa che dipende da un sacco di cose, come:

  • velocità degli aggiornamenti (insert, update, delete)
  • velocità di accesso casuale di recupero
  • velocità sequenziale di recupero
  • memoria utilizzata

Penso che troverete che una struttura di dati che è veloce, generalmente consumano più memoria di quella che è lento.Questo non è sempre il caso, ma la maggior parte delle strutture di dati sembra seguire questo.

Un dizionario può essere facile da usare, e vi darà relativamente uniformemente l'accesso veloce, è molto probabile che l'uso più memoria, come suggerisci tu, elenchi.Elenchi, tuttavia, in genere tendono a contenere più overhead quando si inseriscono dati in esso, a meno che non preallocare X nodi, in cui saranno di nuovo utilizzare più memoria.

Il mio suggerimento, in generale, sarebbe quello di utilizzare solo il metodo che sembra più naturale, e poi fare un "test di stress" del sistema, l'aggiunta di una notevole quantità di dati e vedere se diventa un problema.

Si potrebbe anche prendere in considerazione l'aggiunta di un livello di astrazione di sistema, in modo che non devi cambiare l'interfaccia di programmazione, se poi sulla necessità di modificare la struttura interna dei dati.

Da quanto ho capito, ad accesso casuale è in costante di tempo sia per Python dicts e liste, la differenza è che si può fare solo ad accesso casuale di un numero intero gli indici con le liste.Io parto dal presupposto che è necessario per la ricerca di un nodo dalla sua etichetta, quindi si vuole un dict di dicts.

Tuttavia, le prestazioni fronte, il caricamento in memoria potrebbe non essere un problema, ma se si usa troppo finirete per lo swapping su disco, che uccide la performance anche di Python altamente efficiente dicts.Cercare di mantenere la memoria di utilizzo il più basso possibile.Inoltre, la RAM è incredibilmente basso a destra ora;se si esegue questo tipo di cosa che un sacco, non c'è alcun motivo per non avere almeno 4GB.

Se vuoi consigli su come preservare la memoria di utilizzo giù, dare qualche informazione in più sul tipo di informazioni che si sta monitorando per ogni nodo.

Per rendere una classe-la struttura di base, probabilmente, avrebbe costi superiori rispetto dict-la struttura di base, dal momento che in python classi effettivamente utilizzare dicts quando sono attuate.

Senza dubbio NetworkX è la migliore struttura di dati fino ad ora per il grafico.Si tratta con i programmi come Funzioni di supporto, Algoritmi e Strutture di Dati, di Sequenza Casuale di Generatori, Decoratori, Cuthill-Mckee Ordine, Contesto Gestori

NetworkX è grande perché wowrs per i grafici, digrammi, e multigraphs.È possibile scrivere grafico con diversi modi:Adiacenza Lista, Multiline Adiacenza Elenco Bordo Lista, GEXF, GML.Funziona con Sottaceto, GraphML, JSON, SparseGraph6 etc.

Ha implimentation di varie radimade algoritmi tra cui:Approssimazione, Bipartito, Di Confine, La Centralità, La Cricca, Il Clustering, Colorare, Componenti, Connettività, Cicli, Diretto Aciclico Grafici, Misure Di Distanza, Domina Imposta, Euleriano, Isomorfismo, Link Analysis, Link Di Stima, Di Corrispondenza, Minimum Spanning Tree, Ricco Club, Percorsi Più Brevi, Di Attraversamento, Albero.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top