Wat is de meest efficiënte grafiek datastructuur in Python?

stemmen
63

Ik moet in staat zijn om een grote (10 ^ 7 nodes) grafiek manipuleren python. De gegevens voor elke knoop / edge minimaal bijvoorbeeld een klein aantal snaren. Wat is de meest efficiënte, in termen van het geheugen en de snelheid , manier om dit te doen?

Een dict van dicts is flexibeler en eenvoudiger uit te voeren, maar ik intuïtief verwacht een lijst van lijsten om sneller te zijn. De lijst optie zou ook eisen dat ik blijf de gegevens te scheiden van de structuur, terwijl dicts zou voor iets dergelijks:

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

Wat zou je voorstellen?


Ja, ik zou een beetje duidelijker op wat ik bedoel met efficiency zijn geweest. In dit specifieke geval bedoel ik het in termen van random access retrieval.

Het laden van de data in het geheugen is niet een groot probleem. Dat is eens en voor altijd gedaan. Het tijdrovende deel is een bezoek aan de knooppunten, zodat ik de informatie kan halen en het meten van de metrics Ik ben geïnteresseerd in.

Ik had niet overwogen om elk knooppunt een klasse (eigenschappen zijn hetzelfde voor alle knooppunten), maar het lijkt erop dat dat een extra laag van de overhead zou toevoegen? Ik hoopte dat iemand zou enkele directe ervaring met een soortgelijk geval dat ze kunnen delen. Immers, grafieken zijn een van de meest voorkomende abstracties in CS.

De vraag is gesteld op 04/08/2008 om 13:00
bron van user
In andere talen...                            


7 antwoorden

stemmen
51

Ik zou sterk voorstander je kijkt naar NetworkX . Het is een strijd geteste oorlog paard en het eerste instrument meest 'research' types bereiken voor wanneer ze nodig hebben om de analyse van netwerk-gebaseerde data te doen. Ik heb grafieken met 100s van duizenden kanten gemanipuleerd zonder problemen op een notebook. De functie rijke en zeer makkelijk te gebruiken. Je zult merken dat je de nadruk meer op het probleem bij de hand in plaats van de details in de onderliggende implementatie.

Voorbeeld Erdős-Rényi willekeurige grafiek genereren en analyseren


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

Visualisaties zijn ook eenvoudig:

voer image beschrijving hier

Meer visualisatie: http://jonschull.blogspot.com/2008/08/graph-visualization.html

antwoordde op 26/08/2008 om 18:43
bron van user

stemmen
12

Hoewel deze vraag is nu vrij oud, ik denk dat het de moeite waard om mijn eigen python module voor grafiek manipulatie genoemd vermelden grafiek-instrument . Het is zeer efficiënt, omdat de datastructuren en algoritmen in C ++ worden uitgevoerd, met sjabloon metaprograming, met behulp van de Boost Graph Library. Daarom is de prestaties (zowel in geheugengebruik en runtime) is vergelijkbaar met een zuivere C ++ bibliotheek en kan worden ordes van grootte beter dan de typische python code, zonder in te boeten gebruiksgemak. Ik gebruik het zelf voortdurend om te werken met zeer grote grafieken.

antwoordde op 27/11/2010 om 15:10
bron van user

stemmen
6

Zoals reeds vermeld, NetworkX is zeer goed, met een andere optie zijn igraph . Beide modules zullen de meeste (zo niet alle) van de analyse tools die u waarschijnlijk nodig zijn hebben, en beide bibliotheken worden routinematig gebruikt met grote netwerken.

antwoordde op 27/08/2008 om 11:01
bron van user

stemmen
4

Een woordenboek kan ook overhead bevatten, afhankelijk van de daadwerkelijke uitvoering. Een hash bevatten meestal een prime aantal beschikbare nodes om te beginnen, ook al heb je maar een paar van de knooppunten zou kunnen gebruiken.

Te oordelen naar uw voorbeeld, "Property", zou je beter af met een class benadering voor het eindniveau en onroerende goederen? Of is de namen van de eigenschappen veranderen veel van knooppunt naar knooppunt?

Ik zou zeggen dat wat "efficient" betekent, hangt af van een heleboel dingen, zoals:

  • snelheid van updates (insert, update, delete)
  • snelheid van de random access retrieval
  • snelheid opeenvolgende retrieval
  • geheugen gebruikt

Ik denk dat je zult zien dat een datastructuur die is snel over het algemeen verbruiken meer geheugen dan een die is traag. Dit is niet altijd het geval, maar de meeste datastructuren lijkt dit te volgen.

Een woordenboek kan gemakkelijk te gebruiken, en geven u een relatief gelijkmatig snelle toegang, zal het waarschijnlijk veel geheugengebruik, zoals u voorstelt, lijsten. Lijsten, echter in het algemeen de neiging om meer overhead bevatten wanneer u gegevens in deze in te voegen, tenzij ze preallocate X knooppunten, waar zij weer meer geheugen zal gebruiken.

Mijn suggestie, in het algemeen, zou zijn om gewoon gebruik maken van de methode die de meest natuurlijke lijkt voor u, en doe dan een "stresstest" van het systeem, het toevoegen van een aanzienlijke hoeveelheid data om te zien of het een probleem wordt.

U kunt ook overwegen het toevoegen van een laag van abstractie om uw systeem, zodat u niet hoeft te de programmeerinterface als je later veranderen noodzaak om de interne data structuur te veranderen.

antwoordde op 04/08/2008 om 13:09
bron van user

stemmen
3

Zoals ik het begrijp, random access is in constante tijd voor zowel dicts en lijsten Python's, het verschil is dat u alleen random access van integer indexen met lijsten kunnen doen. Ik ga ervan uit dat je nodig hebt om een ​​knooppunt opzoeken door zijn label, dus je wilt een dict van dicts.

Echter, op de prestaties van de voorkant, het laden in het geheugen is misschien niet een probleem zijn, maar als je te veel te gebruiken zul je uiteindelijk swappen naar schijf, die de prestaties van zelfs zeer efficiënte dicts Python's zal doden. Probeer geheugengebruik omlaag zo veel mogelijk te houden. Ook, RAM-geheugen is nu verbazingwekkend goedkoop; als je dit soort dingen veel doen, is er geen reden om ten minste 4 GB niet te hebben.

Als u wilt advies over het houden geheugengebruik omlaag, geef wat meer informatie over de aard van de informatie die u wilt bijhouden voor elk knooppunt.

antwoordde op 06/08/2008 om 06:37
bron van user

stemmen
2

Het maken van een klasse gebaseerde structuur zou waarschijnlijk hebben meer overhead dan de dict gebaseerde structuur, omdat in python klassen daadwerkelijk gebruik maken van dicts wanneer ze worden uitgevoerd.

antwoordde op 04/08/2008 om 13:41
bron van user

stemmen
1

Ongetwijfeld NetworkX is de beste datastructuur tot nu toe voor de grafiek. Het wordt geleverd met utilities zoals Helper functies, datastructuren en algoritmen, willekeurige volgorde Generators, decorateurs, Cuthill-Mckee Bestellen, Context Managers

NetworkX is geweldig omdat het wowrs voor grafieken, digraphs en multigraphs. Het kan grafiek schrijven met meerdere manieren: Adjacency List, Multiline Adjacency List, Edge List, GEXF, GML. Het werkt met Pickle, GraphML, JSON, SparseGraph6 etc.

Het heeft implimentation van diverse radimade algoritmen, waaronder: de aanpassing, Bipartiete, Begrenzing, Centrality, Clique, Clustering, Coloring, Components, Connectiviteit, Cycles, Directed Acyclische grafieken, Distance Measures, dominerende verzameling, Eulerian, isomorfisme, Link Analysis, Link Voorspelling, bijpassende , minimale Spanning Tree, Rich Club, kortste paden, Traversal, Boom.

antwoordde op 18/01/2016 om 09:08
bron van user

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