Umwandlung einer 1,2 GB großen Liste von Kanten in eine dünne Matrix

Ich habe eine Liste mit 1,2 GB Kanten aus einem Diagramm in einer Textdatei. Mein Ubuntu-PC hat 8 GB RAM. Jede Zeile in der Eingabe sieht aus wie

287111206 357850135

Ich möchte es in eine spärliche Adjazenzmatrix konvertieren und diese in eine Datei ausgeben.

Einige Statistiken für meine Daten:

Number of edges: around 62500000
Number of vertices: around 31250000

Ich habe viel die gleiche Frage gestellt, bevor beihttps: //stackoverflow.com/a/38667644/217902 und bekam eine tolle Antwort. Das Problem ist, dass ich es nicht zum Laufen bringen kann.

Ich habe zuerst versucht, np.loadtxt in die Datei zu laden, aber sie war sehr langsam und beanspruchte sehr viel Speicher. Also bin ich stattdessen zu pandas.read_csv gewechselt, was sehr schnell ist, aber es hat eigene Probleme verursacht. Das ist mein aktueller Code:

import pandas
import numpy as np
from scipy import sparse

data = pandas.read_csv("edges.txt", sep=" ", header= None, dtype=np.uint32)
A = data.as_matrix()
print type(A)
k1,k2,k3=np.unique(A,return_inverse=True,return_index=True)
rows,cols=k3.reshape(A.shape).T
M=sparse.coo_matrix((np.ones(rows.shape,int),(rows,cols)))
print type(M)

Das Problem ist, dass der Pandas DataFramedata ist riesig und ich mache effektiv eine Kopie in A, was ineffizient ist. Die Situation ist jedoch noch schlimmer, da der Code mit @ abstürz

<type 'instancemethod'>
Traceback (most recent call last):
  File "make-sparse-matrix.py", line 13, in <module>
    rows,cols=k3.reshape(A.shape).T
AttributeError: 'function' object has no attribute 'shape'
raph@raph-desktop:~/python$ python make-sparse-matrix.py 
<type 'numpy.ndarray'>
Traceback (most recent call last):
  File "make-sparse-matrix.py", line 12, in <module>
    k1,k2,k3=np.unique(A,return_inverse=True,return_index=True)
  File "/usr/local/lib/python2.7/dist-packages/numpy/lib/arraysetops.py", line 209, in unique
    iflag = np.cumsum(flag) - 1
  File "/usr/local/lib/python2.7/dist-packages/numpy/core/fromnumeric.py", line 2115, in cumsum
    return cumsum(axis, dtype, out)
MemoryError

Also meine Fragen sind:

Kann ich vermeiden, dass sowohl der 1,2-GB-Pandas-Datenrahmen als auch die 1,2-GB-Numpy-Array-Kopie im Speicher gespeichert werden? Gibt es eine Möglichkeit, den Code in 8 GB RAM zu vervollständigen?

Sie können eine Testeingabe in der Größe reproduzieren, mit der ich sie verarbeiten möchte:

import random
#Number of edges, vertices
m = 62500000
n = m/2
for i in xrange(m):
    fromnode = str(random.randint(0, n-1)).zfill(9)
    tonode = str(random.randint(0, n-1)).zfill(9)
    print fromnode, tonode

Aktualisiere

Ich habe jetzt verschiedene Ansätze ausprobiert, die alle gescheitert sind. Hier ist eine Zusammenfassung.

Using igraph mitg = Graph.Read_Ncol('edges.txt'). Dies verbraucht sehr viel RAM, was meinen Computer zum Absturz bringt.Using networkit mitG= networkit.graphio.readGraph("edges.txt", networkit.Format.EdgeList, separator=" ", continuous=False). Dies verbraucht sehr viel RAM, was meinen Computer zum Absturz bringt.Der Code oben in dieser Frage, aber mit np.loadtxt ("edges.txt") anstelle von Pandas. Dies verbraucht sehr viel RAM, was meinen Computer zum Absturz bringt.

Ich habe dann einen separaten Code geschrieben, der alle Scheitelpunktnamen einer Zahl von 1 ... | V | zuordnet wo | V | ist die Gesamtzahl der Eckpunkte. Dies sollte den Code, der die Kantenliste importiert, davor bewahren, eine Tabelle zu erstellen, die die Scheitelpunktnamen abbildet. Damit habe ich versucht:

Mit dieser neuen neu zugeordneten Kantenlistendatei habe ich igraph erneut mit @ verwendeg = Graph.Read_Edgelist("edges-contig.txt"). Dies funktioniert jetzt, obwohl es 4 GB RAM benötigt (das ist weit mehr als die theoretische Menge, die es sollte). Es gibt jedoch keine Igraph-Funktion, um eine dünn besetzte Adjazenzmatrix aus einem Graphen herauszuschreiben. Die empfohlene Lösung ist Konvertiere den Graphen in eine coo_matrix. Leider verbraucht dies sehr viel RAM, was meinen Computer zum Absturz bringt.Verwenden Sie die neu zugeordnete Edge-List-Datei, die ich mit networkit zusammen mit @ verwendet habG = networkit.readGraph("edges-contig.txt", networkit.Format.EdgeListSpaceOne). Dies funktioniert auch mit weniger als den 4 GB, die igraph benötigt. networkit enthält auch eine Funktion zum Schreiben von Matlab-Dateien (eine Form von spärlicher Adjazenzmatrix, die scipy lesen kann). Jedochnetworkit.graphio.writeMat(G,"test.mat") verbraucht sehr viel RAM, wodurch mein Computer abstürzt.

Endlich ist die Antwort von Sascha vollständig, dauert aber ungefähr 40 Minuten.