Eu tenho uma lista de bordas de 1,2 GB de um gráfico em um arquivo de texto. Meu PC ubuntu possui 8 GB de RAM. Cada linha na entrada se parece com

287111206 357850135

Gostaria de convertê-lo em uma matriz de adjacência esparsa e enviá-la para um arquivo.

Algumas estatísticas para meus dados:

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

Eu fiz a mesma pergunta antes emhttps://stackoverflow.com/a/38667644/2179021 e recebi uma ótima resposta. O problema é que não consigo fazê-lo funcionar.

Eu tentei primeiro carregar o arquivo np.loadtxt, mas era muito lento e utilizava uma quantidade enorme de memória. Então mudei para pandas.read_csv, que é muito rápido, mas isso causou problemas. Este é o meu código atual:

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)

O problema é que o dataframe do pandasdata é enorme e estou efetivamente fazendo uma cópia em A que é ineficiente. No entanto, as coisas são ainda piores, pois o código trava com

<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

Então, minhas perguntas são:

Posso evitar a cópia do dataframe de pandas de 1,2 GB e da matriz numpy de 1,2 GB na memória?Existe alguma maneira de obter o código completo em 8 GB de RAM?

Você pode reproduzir uma entrada de teste do tamanho com o qual estou tentando processar:

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

Atualizar

Eu já tentei várias abordagens diferentes, todas as quais falharam. Aqui está um resumo.

Usandoigraph comg = Graph.Read_Ncol('edges.txt'). Isso usa uma quantidade enorme de RAM que trava meu computador.Usandonetworkit comG= networkit.graphio.readGraph("edges.txt", networkit.Format.EdgeList, separator=" ", continuous=False). Isso usa uma quantidade enorme de RAM que trava meu computador.O código acima nesta pergunta, mas usando np.loadtxt ("edge.txt") em vez de pandas. Isso usa uma quantidade enorme de RAM que trava meu computador.

Escrevi então um código separado que remapeava todos os nomes dos vértices para numerar de 1 .. | V | onde | V | é o número total de vértices. Isso deve evitar que o código que importa a lista de arestas precise criar uma tabela que mapeie os nomes dos vértices. Usando isso, tentei:

Usando este novo arquivo de lista de arestas remapeadas, usei o igraph novamente comg = Graph.Read_Edgelist("edges-contig.txt"). Isso agora funciona, embora consuma 4 GB de RAM (que é muito mais do que a quantidade teórica que deveria). No entanto, não há função igraph para escrever uma matriz de adjacência esparsa de um gráfico. A solução recomendada éconverter o gráfico em um coo_matrix. Infelizmente, isso usa uma quantidade enorme de RAM que trava meu computador.Usando o arquivo de lista de arestas remapeado, usei o networkit comG = networkit.readGraph("edges-contig.txt", networkit.Format.EdgeListSpaceOne). Isso também funciona com menos de 4 GB que o igraph precisa. O networkit também vem com uma função para gravar arquivos Matlab (que é uma forma de matriz de adjacência esparsa que o scipy pode ler). Contudonetworkit.graphio.writeMat(G,"test.mat") usa uma enorme quantidade de RAM que trava meu computador.

Finalmente, a resposta de sascha abaixo é concluída, mas leva cerca de 40 minutos.