Was ist die effizienteste Diagrammdatenstruktur in Python?[geschlossen]

Question

Ich muss in der Lage sein, ein großes Diagramm (10 ^ 7 Knoten) in Python zu bearbeiten.Die jedem Knoten/jeder Kante entsprechenden Daten sind minimal, beispielsweise eine kleine Anzahl von Zeichenfolgen.Was ist am effizientesten in Bezug auf? Gedächtnis und Geschwindigkeit, wie geht das?

Ein Diktat von Diktaten ist flexibler und einfacher zu implementieren, aber ich erwarte intuitiv, dass eine Liste von Listen schneller ist.Die Listenoption würde auch erfordern, dass ich die Daten von der Struktur getrennt halte, während Diktate etwas in der Art ermöglichen würden:

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

Was würdest du vorschlagen?

---

Ja, ich hätte etwas klarer sagen sollen, was ich unter Effizienz verstehe.In diesem speziellen Fall meine ich es im Hinblick auf den Direktzugriffsabruf.

Das Laden der Daten in den Speicher ist kein großes Problem.Das ist ein für alle Mal erledigt.Der zeitaufwändige Teil besteht darin, die Knoten zu besuchen, damit ich die Informationen extrahieren und die Metriken messen kann, die mich interessieren.

Ich hatte nicht darüber nachgedacht, jeden Knoten zu einer Klasse zu machen (die Eigenschaften sind für alle Knoten gleich), aber es sieht so aus, als würde das einen zusätzlichen Overhead verursachen?Ich hatte gehofft, dass jemand direkte Erfahrungen mit einem ähnlichen Fall hätte, die er teilen könnte.Schließlich sind Diagramme eine der häufigsten Abstraktionen in CS.

Answer 1

Ich würde Ihnen dringend empfehlen, sich das anzusehen NetzwerkX.Es ist ein kampferprobtes Kriegspferd und das erste Werkzeug, zu dem die meisten Forscher greifen, wenn sie netzwerkbasierte Daten analysieren müssen.Ich habe Diagramme mit Hunderttausenden Kanten problemlos auf einem Notebook manipuliert.Es verfügt über zahlreiche Funktionen und ist sehr einfach zu bedienen.Sie werden feststellen, dass Sie sich mehr auf das vorliegende Problem als auf die Details der zugrunde liegenden Implementierung konzentrieren.

Beispiel von Erdős-Rényi Zufallsdiagrammgenerierung und -analyse

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

Auch Visualisierungen sind unkompliziert:

Mehr Visualisierung: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Answer 2

Auch wenn diese Frage mittlerweile ziemlich alt ist, denke ich, dass es sich lohnt, mein eigenes Python-Modul zur Diagrammmanipulation namens „ Diagramm-Tool.Es ist sehr effizient, da die Datenstrukturen und Algorithmen in C++ mit Template-Metaprogrammierung unter Verwendung der Boost Graph Library implementiert sind.Daher ist seine Leistung (sowohl bei der Speichernutzung als auch bei der Laufzeit) mit einer reinen C++-Bibliothek vergleichbar und kann um Größenordnungen besser sein als typischer Python-Code, ohne dass die Benutzerfreundlichkeit darunter leidet.Ich selbst verwende es ständig, um mit sehr großen Diagrammen zu arbeiten.

Answer 3

Wie bereits erwähnt, ist NetworkX sehr gut, mit einer weiteren Option igraph.Beide Module verfügen über die meisten (wenn nicht alle) Analysetools, die Sie wahrscheinlich benötigen, und beide Bibliotheken werden routinemäßig in großen Netzwerken verwendet.

Answer 4

Abhängig von der tatsächlichen Implementierung kann ein Wörterbuch auch Overhead enthalten.Eine Hashtabelle enthält normalerweise zunächst eine Primzahl verfügbarer Knoten, auch wenn Sie möglicherweise nur einige der Knoten verwenden.

Anhand Ihres Beispiels „Immobilien“ zu urteilen, wäre ein Klassenansatz für die letzte Ebene und Immobilien besser geeignet?Oder ändern sich die Namen der Eigenschaften von Knoten zu Knoten stark?

Ich würde sagen, was „effizient“ bedeutet, hängt von vielen Dingen ab, wie zum Beispiel:

• Geschwindigkeit der Aktualisierungen (Einfügen, Aktualisieren, Löschen)
• Geschwindigkeit des Direktzugriffsabrufs
• Geschwindigkeit des sequentiellen Abrufs
• Speicher verwendet

Ich denke, Sie werden feststellen, dass eine schnelle Datenstruktur im Allgemeinen mehr Speicher verbraucht als eine langsame.Dies ist nicht immer der Fall, aber die meisten Datenstrukturen scheinen dem zu folgen.

Ein Wörterbuch ist möglicherweise einfach zu verwenden und ermöglicht einen relativ gleichmäßig schnellen Zugriff. Es verbraucht jedoch höchstwahrscheinlich mehr Speicher als Listen, wie Sie vorschlagen.Listen neigen jedoch im Allgemeinen dazu, mehr Overhead zu verursachen, wenn Sie Daten in sie einfügen, es sei denn, sie weisen vorab X-Knoten zu, in denen sie wiederum mehr Speicher verbrauchen.

Im Allgemeinen würde ich vorschlagen, einfach die Methode zu verwenden, die Ihnen am natürlichsten erscheint, und dann einen „Stresstest“ des Systems durchzuführen, indem Sie ihm eine beträchtliche Datenmenge hinzufügen und prüfen, ob es zu einem Problem wird.

Sie könnten auch darüber nachdenken, Ihrem System eine Abstraktionsebene hinzuzufügen, damit Sie die Programmierschnittstelle nicht ändern müssen, wenn Sie später die interne Datenstruktur ändern müssen.

Answer 5

Soweit ich weiß, erfolgt der Direktzugriff sowohl für Pythons Diktate als auch für Listen in konstanter Zeit. Der Unterschied besteht darin, dass Sie mit Listen nur Direktzugriff auf Integer-Indizes durchführen können.Ich gehe davon aus, dass Sie einen Knoten anhand seiner Bezeichnung suchen müssen, also möchten Sie ein Diktat von Diktaten.

Was die Leistung anbelangt, stellt das Laden in den Speicher möglicherweise kein Problem dar. Wenn Sie jedoch zu viel davon verwenden, wechseln Sie am Ende auf die Festplatte, was die Leistung selbst der hocheffizienten Diktate von Python beeinträchtigt.Versuchen Sie, die Speichernutzung so gering wie möglich zu halten.Außerdem ist RAM derzeit erstaunlich günstig;Wenn Sie so etwas häufig tun, gibt es keinen Grund, nicht mindestens 4 GB zu haben.

Wenn Sie Ratschläge zur Reduzierung der Speichernutzung benötigen, geben Sie weitere Informationen zu der Art der Informationen an, die Sie für jeden Knoten verfolgen.

Answer 6

Das Erstellen einer klassenbasierten Struktur würde wahrscheinlich mehr Aufwand verursachen als die dict-basierte Struktur, da Klassen in Python tatsächlich Diktate verwenden, wenn sie implementiert werden.

Answer 7

Zweifellos ist NetworkX bisher die beste Datenstruktur für Grafiken.Es enthält Dienstprogramme wie Hilfsfunktionen, Datenstrukturen und Algorithmen, Zufallssequenzgeneratoren, Dekoratoren, Cuthill-Mckee-Reihenfolge und Kontextmanager

NetworkX ist großartig, weil es sich hervorragend für Diagramme, Digraphen und Multigraphen eignet.Es kann auf verschiedene Arten ein Diagramm schreiben:Adjazenzliste, Multiline -Adjazenzliste, Kantenliste, GEXF, GML.Es funktioniert mit Pickle, GraphML, JSON, SparseGraph6 usw.

Es verfügt über die Implementierung verschiedener Radimade-Algorithmen, darunter:Annäherung, Bipartiten, Grenze, Zentralität, Clique, Clustering, Färbung, Komponenten, Konnektivität, Zyklen, gerichtete acyclische Graphen, Distanzmessungen, dominierende Sets, Eulerianer, Isomorphismus, Verbindungsanalyse, Linkvorhersage, Matching, minimaler Spannungsbaum, reichhaltiges Club, kürzester Wege, Traversal, Baum.