Care este cea mai eficientă structură de date grafic în Python?

voturi
63

Trebuie să fie capabil să manipuleze un (10 ^ 7 noduri) , grafic mai mare în Python. Datele corespunzătoare fiecărui nod / muchie este minimă, să zicem, un număr mic de siruri de caractere. Care este cel mai eficient, în termeni de memorie și viteza , mod de a face acest lucru?

O dict de dicts este mai flexibil și mai simplu de implementat, dar mă aștept intuitiv o listă de liste pentru a fi mai rapid. Opțiunea listă ar necesita, de asemenea, că am să păstreze datele separat de structura, in timp ce dicts ar permite ceva de genul:

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

Ce-ai sugera?


Da, aș fi fost un pic mai clar asupra a ceea ce vreau să spun de eficiență. În acest caz particular mă refer în termeni de regăsire cu acces aleator.

Se încarcă datele din memoria nu este o problemă uriașă. Asta a făcut o dată pentru totdeauna. Partea consumatoare de timp este de a vizita nodurile, astfel că pot extrage informațiile și măsurați valorile Sunt interesat.

N-am considerat a face fiecare nod o clasă (proprietăți sunt aceleași pentru toate nodurile), dar se pare ca asta ar adăuga un strat suplimentar de deasupra capului? Am fost în speranța cineva ar avea o anumită experiență directă cu un caz similar pe care le-ar putea împărtăși. La urma urmei, graficele sunt una dintre cele mai comune abstracțiuni din CS.

Întrebat 04/08/2008 la 13:00
sursa de către utilizator
În alte limbi...                            


7 răspunsuri

voturi
51

Aș puternic avocat te uiți la NetworkX . Este un cal de război testat de luptă și primul instrument de cele mai multe tipuri de cercetare „“ pentru a ajunge atunci când au nevoie pentru a face analiza datelor bazate pe rețea. Am manipulat grafice cu 100s de mii de margini fără probleme pe un notebook. Caracteristica sa bogată și foarte ușor de utilizat. Veți găsi te concentrându - se mai mult pe problema la îndemână , mai degrabă decât detaliile în implementarea de bază.

Exemplu de Erdős-Rényi generație grafic aleatorii și analiză


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

Vizualizările sunt de asemenea simplu:

introduceți descrierea imaginii aici

Mai multe vizualizare: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Publicat 26/08/2008 la 18:43
sursa de către utilizator

voturi
12

Chiar dacă această întrebare este acum destul de vechi, cred că merită să menționăm propriul meu modul Python pentru manipulare grafic numit grafic-instrument . Este foarte eficient, deoarece structurile de date și algoritmi sunt implementate în C ++, cu șablonul metaprograming, folosind Boost Graph Library. Prin urmare , performanțele sale (atât în utilizarea memoriei și de execuție) este comparabil cu o bibliotecă C ++ pură, și poate fi ordine de mărime mai bună decât codul Python tipic, fără a sacrifica ușurința de utilizare. L folosesc eu în mod constant pentru a lucra cu grafice foarte mari.

Publicat 27/11/2010 la 15:10
sursa de către utilizator

voturi
6

După cum sa menționat deja, NetworkX este foarte bun, cu o altă opțiune fiind igraph . Ambele module vor avea cele mai multe (dacă nu toate) instrumentele de analiză pe care este posibil să aibă nevoie, și ambele biblioteci sunt folosite in mod curent cu rețele mari.

Publicat 27/08/2008 la 11:01
sursa de către utilizator

voturi
4

Un dicționar poate conține, de asemenea deasupra capului, în funcție de punerea în aplicare efectivă. Un hashtable conțin, de obicei, unele număr prim de noduri disponibile pentru a începe cu, chiar dacă s-ar putea folosi doar o pereche de noduri.

Judecând după exemplul dumneavoastră, „proprietate“, te-ai fi mai bine de o abordare de clasă pentru nivelul final și proprietățile reale? Sau este numele proprietăților în schimbare o mulțime de la nod la altul?

Aș spune că ceea ce „eficientă“ înseamnă depinde de o mulțime de lucruri, cum ar fi:

  • Viteza de actualizări (insert, update, șterge)
  • viteza de regăsire acces aleator
  • viteza de regăsire secvențială
  • memoria utilizată

Cred că veți găsi că o structură de date care este voința rapidă, în general, consumă mai multă memorie decât una care este lent. Acest lucru nu este întotdeauna cazul, dar cele mai multe structuri de date pare să urmeze acest lucru.

Un dicționar ar putea fi ușor de utilizat, și de a vă oferi acces relativ uniform rapid, se va folosi cel mai probabil, mai multă memorie decât, după cum sugerează, liste. Liste, cu toate acestea, în general, tind să conțină mai mult deasupra capului atunci când introduceți date în ea, cu excepția cazului în care prealoca nodurile X, în care se vor folosi din nou mai multă memorie.

Sugestia mea, în general, ar fi de a folosi doar metoda care pare cel mai natural pentru tine, și apoi a face un „test de stres“ a sistemului, adăugând o cantitate substanțială de date către ea și a vedea dacă acesta devine o problemă.

S-ar putea lua în considerare, de asemenea, adăugarea unui strat de abstractizare a sistemului, astfel încât să nu trebuie să modificați interfața de programare în cazul în care aveți mai târziu necesitatea de a schimba structura internă a datelor.

Publicat 04/08/2008 la 13:09
sursa de către utilizator

voturi
3

După cum am înțeles, cu acces aleator este în timp constant, pentru ambele dicts și listele de Python, diferența este că se poate face doar cu acces aleator de indici întregi cu liste. Sunt presupunând că aveți nevoie să căutare un nod de eticheta, astfel încât să doriți o dict de dicts.

Cu toate acestea, pe frontul de performanță, încărcarea acestuia în memoria poate să nu fie o problemă, dar dacă utilizați prea mult veți termina schimbarea pe disc, care va ucide performanța chiar dicts extrem de eficiente Python. Încercați să păstrați utilizarea de memorie în jos cât mai mult posibil. De asemenea, memoria RAM este uimitor de ieftin chiar acum; dacă faci acest tip de lucru mult, nu există nici un motiv să nu aibă cel puțin 4 GB.

Dacă doriți sfaturi cu privire la păstrarea utilizarea memoriei în jos, da unele mai multe informații despre tipul de informații pe care le urmăriți pentru fiecare nod.

Publicat 06/08/2008 la 06:37
sursa de către utilizator

voturi
2

Realizarea unei structuri bazate pe clasă ar avea, probabil, mai mult deasupra capului decât structura bazată pe dict, deoarece în clasele Python folosesc de fapt dicts atunci când acestea sunt puse în aplicare.

Publicat 04/08/2008 la 13:41
sursa de către utilizator

voturi
1

Fără îndoială NetworkX este cea mai buna structura de date pana in prezent pentru grafic. Acesta este dotat cu utilități, cum ar fi funcții Helper, structuri de date și algoritmi, generatoare ordine aleatoare, decoratori, Cuthill-Mckee comandă, manageri de context

NetworkX este mare, pentru că wowrs pentru grafice, digraphs și multigraphs. Se poate scrie grafic cu mai multe moduri: adiacență List, Multiline adiacență List, List Edge, GEXF, GML. Acesta funcționează cu Pickle, GraphML, JSON, SparseGraph6 etc.

Are implimentation de diferite algoritmi radimade, inclusiv: Apropierea, bipartit, limită, centralitate, Clique, clustering, colorat, Componente, Conectivitate, Cicluri, Directed aciclic grafice, măsuri la distanță, Seturi Dominând, Eulerian, izomorfism, Analiza Link, Link Predicție, de potrivire , minim Spanning copac, rich Club, drumuri, traversare, copac.

Publicat 18/01/2016 la 09:08
sursa de către utilizator

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