Ich habe eine 1,2 GB-Liste von Kanten aus einem Graphen in einer Textdatei. Mein ubuntu PC hat 8GB RAM. Jede Zeile in der Eingabe sieht wie
aus %Vor%Ich möchte es in eine spärliche Adjazenzmatrix konvertieren und diese in eine Datei ausgeben.
Einige Statistiken für meine Daten:
%Vor%Ich habe die gleiche Frage schon vorher bei Ссылка gestellt und eine tolle Antwort bekommen. Das Problem ist, dass ich es nicht zum Laufen bringen kann.
Ich habe zuerst versucht, np.loadtxt in die Datei zu laden, aber es war sehr langsam und verwendete eine riesige Menge an Speicher. Also bin ich stattdessen zu pandas.read_csv gewechselt, was sehr schnell ist, aber das hat zu eigenen Problemen geführt. Dies ist mein aktueller Code:
%Vor% Das Problem ist, dass der Pandas Dataframe data sehr groß ist und ich effektiv eine Kopie in A mache, was ineffizient ist. Allerdings sind die Dinge noch schlimmer, wenn der Code mit
Meine Fragen sind also:
Sie können eine Testeingabe der Größe reproduzieren, mit der ich versuchen möchte:
%Vor%Aktualisieren
Ich habe jetzt eine Reihe verschiedener Ansätze ausprobiert, die alle gescheitert sind. Hier ist eine Zusammenfassung.
g = Graph.Read_Ncol('edges.txt') . Dies verwendet eine große Menge an RAM, die meinen Computer abstürzt. G= networkit.graphio.readGraph("edges.txt",
networkit.Format.EdgeList, separator=" ", continuous=False) . Dies verwendet eine große Menge an RAM, die meinen Computer abstürzt. Ich habe dann einen separaten Code geschrieben, der alle Eckennamen von 1 .. | V | wo | V | ist die Gesamtzahl der Ecken. Dadurch sollte der Code, der die Kantenliste importiert, davor bewahrt werden, eine Tabelle erstellen zu müssen, die die Scheitelpunktnamen abbildet. Mit diesem versuchte ich:
g = Graph.Read_Edgelist("edges-contig.txt") verwendet. Dies funktioniert jetzt, obwohl es 4 GB RAM benötigt (was viel mehr ist als die theoretische Menge, die es sollte). Es gibt jedoch keine Funktion, um aus einem Graph eine spärliche Adjazenzmatrix herauszuschreiben. Die empfohlene Lösung besteht darin, das Diagramm in eine coo_matrix zu konvertieren. Leider verwendet dies eine riesige Menge an RAM, die meinen Computer abstürzt. G = networkit.readGraph("edges-contig.txt", networkit.Format.EdgeListSpaceOne) verwendet. Dies funktioniert auch mit weniger als 4 GB, die benötigt werden. Networkit enthält auch eine Funktion zum Schreiben von Matlab-Dateien (eine Form der spärlichen Adjazenzmatrix, die scipy lesen kann). Allerdings verwendet networkit.graphio.writeMat(G,"test.mat") eine riesige Menge RAM, die meinen Computer zum Absturz bringt. Schließlich ist Saschas Antwort unten fertig, dauert aber ungefähr 40 Minuten.
Hier ist meine Lösung:
%Vor% Pandas macht das Parsen mit read_csv schwer. Und Pandas speichert die Daten bereits im Spaltenformat. Die data[0] und data[1] erhalten nur Referenzen, keine Kopien. Dann füttere ich diese an coo_matrix . Benchmarked lokal:
Dann um eine CSR-Matrix in eine Datei zu speichern:
%Vor%Benchmarked lokal:
%Vor%Und später laden Sie es aus einer Datei zurück:
%Vor%Benchmarked lokal:
%Vor%Und schließlich alles testen:
%Vor% Wenn test() ausgeführt wird, dauert es etwa 30 Sekunden:
Und der Speicher High-Water-Mark war ~ 1,79 GB.
Beachten Sie, dass nach dem Konvertieren von "kanten.txt" nach "kanten.npz" im CSR-Matrix-Format das Laden weniger als eine Sekunde dauert.
Wie in den Kommentaren angegeben, passte der Ansatz nicht zu Ihrem Anwendungsfall. Lassen Sie uns einige Änderungen vornehmen:
Dieser Ansatz dauert ~ 45 Minuten (das ist langsam; aber Sie können das Ergebnis pickle / speichern, so dass Sie nur einmal machen müssen) und ~ 5 GB Speicher zur Vorbereitung der Sparse-Matrix für Ihre Daten, generiert mit:
%Vor%Hier ist ein sehr einfacher und sehr ineffizienter (in Bezug auf Zeit und Raum) Code, um diese spärliche Matrix zu erstellen. Ich poste diesen Code, weil ich glaube, dass es wichtig ist, die Kernteile zu verstehen, wenn man diese in etwas Größerem verwendet.
Lassen Sie uns sehen, ob dieser Code für Ihren Anwendungsfall effizient genug ist oder ob er funktioniert. Aus der Entfernung ist es schwer zu sagen, weil wir Ihre Daten nicht haben.
Der Wörterbuchteil, der für das Mapping verwendet wird, ist ein Kandidat, um Ihr Gedächtnis in die Luft zu jagen. Aber es ist sinnlos, dies zu optimieren, ohne zu wissen, ob es überhaupt benötigt wird. Vor allem, weil dieser Teil des Codes von der Anzahl der Scheitelpunkte in Ihrem Graph abhängt (und ich habe keine Kenntnis von dieser Kardinalität).
%Vor%Ausgabe für Kanten-10.txt :
%Vor%Ich habe die verschiedenen verfügbaren Methoden abgesehen von den bereits verwendeten Methoden ausprobiert. Ich fand Folgendes gut.
Methode 1 - Lesen Sie die Datei in eine Zeichenfolge und analysieren Sie die Zeichenfolge in eine 1-D-Array mit numpy fromstring.
%Vor%Ausgabe:
%Vor%Methode 2 - Wie Methode 1, außer dass die Datei nicht in eine Zeichenfolge geladen wird, sondern die Speicherabbildschnittstelle verwendet wird.
%Vor%Ausgabe:
%Vor% Überwacht mit /usr/bin/time , beide Methoden verwenden maximal ca. 2 GB Arbeitsspeicher.
Wenige Anmerkungen:
Es scheint etwas besser zu sein als Pandas read_csv . Mit pandas read_csv ist die Ausgabe auf demselben Rechner
5 loops, best of 3: 16.2 s per loop
Die Umstellung von COO auf CSR / CSC verbraucht ebenfalls viel Zeit. In @ GrantJ's Antwort dauert es weniger Zeit, da die Initialisierung der COO-Matrix nicht korrekt ist. Das Argument muss als Tupel angegeben werden. Ich wollte hier einen Kommentar hinterlassen, aber ich habe noch keine Kommentarrechte.
Meine Vermutung, warum dies etwas besser ist als Pandas read_csv ist die vorherige Annahme von 1D-Daten.
In meiner Antwort betrachte ich den Fall, in dem die IDs der Knoten durch 9 Zeichen lange Zeichenfolgen für jedes Zeichen von [0-9A-Za-z] gegeben sind. n dieser Knoten-IDs sollten auf die Werte [0,n-1] abgebildet werden (was für Ihre Anwendung möglicherweise nicht notwendig ist, aber dennoch von allgemeinem Interesse ist).
Die nächsten Überlegungen, von denen Sie sicherlich wissen, sind hier der Vollständigkeit halber:
10^8 strings in der Datei. string + int32 -Wertpaar kostet um 120 Bytes in einem Wörterbuch, was zu einer Speicherauslastung von 12 GB für die Datei führt. int64 abgebildet werden: Es gibt 62 verschiedene Zeichen - & gt; kann mit 6 Bits, 9 Zeichen im String codiert werden - & gt; 6 * 9 = 54 & lt; 64 Bit. Siehe auch toInt64() Methode weiter unten. array.array könnte alternativ sein, aber wir verwenden np.array (weil es Sortieralgorithmen für np.array gibt, aber nicht array.array ). 1. step: Lesen der Datei und Zuordnen von Zeichenfolgen zu int64 . Es ist ein Schmerz, eine np.array dynamisch wachsen zu lassen, also nehmen wir jetzt die Anzahl der Kanten in der Datei an (es wäre schön, sie in der Kopfzeile zu haben, aber sie kann auch aus der Dateigröße abgeleitet werden):
2. step: konvertiert die int64-Werte in Werte [0,n-1] :
Möglichkeit A , benötigt 3 * 0.8GB:
%Vor%Möglichkeit B , benötigt 2 * 0.8GB, ist aber etwas langsamer:
%Vor%3. step: setze alles in coo_matrix:
%Vor% Für den Aufruf von data_as_coo_matrix("data.txt", 62500000) benötigt der Speicher Spitzen bei 2,5 GB (aber mit int32 anstelle von int64 werden nur 1,5 GB benötigt). Es dauerte ungefähr 5 Minuten auf meiner Maschine, aber meine Maschine ist ziemlich langsam ...
Was unterscheidet sich also von Ihrer Lösung?
np.unique (und nicht alle Indizes und die Umkehrung), so dass etwas Speicher gespart wird - ich kann die alten IDs durch die neuen In-Place ersetzen. pandas , also ist vielleicht etwas kopiert zwischen pandas & lt; - & gt; numpy Datenstrukturen? Was ist der Unterschied zu Saschas Lösung?
np.unique() . Die Lösung von sascha hält die Liste die ganze Zeit sortiert - Sie müssen dafür zumindest mit einem konstanten Faktor bezahlen, auch wenn die Laufzeit O(n log(n)) bleibt. Ich nahm an, dass ein add-Vorgang wäre O(n) , aber wie bereits erwähnt, ist es O(log(n) . Was ist der Unterschied zur Lösung von GrantJ?
NxN - mit N - Anzahl der verschiedenen Knoten und nicht 2^54x2^54 (mit sehr vielen leeren Zeilen und Spalten). PS:
Hier ist meine Idee, wie die 9 Zeichenfolgen-ID auf einen int64 Wert abgebildet werden kann, aber ich denke, dass diese Funktion ein Flaschenhals werden könnte, wie er geschrieben wurde und optimiert werden sollte.
Tags und Links python optimization numpy pandas scipy