Преобразование списка ребер размером 1,2 ГБ в разреженную матрицу

У меня есть список ребер 1,2 ГБ из графика в текстовом файле. Мой компьютер с Ubuntu имеет 8 ГБ оперативной памяти. Каждая строка на входе выглядит так

287111206 357850135

Я хотел бы преобразовать его в матрицу разреженной смежности и вывести ее в файл.

Немного статистики по моим данным:

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

Я задал тот же вопрос, прежде чем вhttps://stackoverflow.com/a/38667644/2179021 и получил отличный ответ. Проблема в том, что я не могу заставить его работать.

Сначала я попытался загрузить файл np.loadtxt, но он был очень медленным и занимал огромное количество памяти. Поэтому вместо этого я перешел на pandas.read_csv, который работает очень быстро, но это вызвало его собственные проблемы. Это мой текущий код:

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)

Проблема в том, что датафрейм пандdata огромен, и я эффективно делаю копию в A, которая неэффективна. Однако все еще хуже, так как код падает с

<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

Итак, мои вопросы:

Могу ли я избежать хранения в памяти как данных панелей 1,2 ГБ Pandas, так и копий массива 1,2 ГБ?Есть ли способ получить код для завершения в 8 ГБ ОЗУ?

Вы можете воспроизвести тестовый ввод того размера, который я пытаюсь обработать:

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

Обновить

Сейчас я попробовал несколько разных подходов, но все они потерпели неудачу. Вот краткое изложение.

С помощьюigraph сg = Graph.Read_Ncol('edges.txt'), Это использует огромное количество оперативной памяти, которая приводит к поломке моего компьютера.С помощьюnetworkit сG= networkit.graphio.readGraph("edges.txt", networkit.Format.EdgeList, separator=" ", continuous=False), Это использует огромное количество оперативной памяти, которая приводит к поломке моего компьютера.Код выше в этом вопросе, но с использованием np.loadtxt ("dge.txt ") вместо панд. Это использует огромное количество оперативной памяти, которая приводит к поломке моего компьютера.

Затем я написал отдельный код, который переназначил все имена вершин на числа от 1 .. | V | где | V | общее количество вершин. Это должно сохранить код, импортирующий список ребер, от необходимости создавать таблицу, отображающую имена вершин. Используя это, я попытался:

Используя этот новый переназначенный файл списка ребер, я снова использовал igraph сg = Graph.Read_Edgelist("edges-contig.txt"), Теперь это работает, хотя требуется 4 ГБ ОЗУ (что намного больше теоретического объема, который должен). Тем не менее, нет функции igraph для записи разреженной матрицы смежности из графа. Рекомендуемое решение заключается впреобразовать график в coo_matrix, К сожалению, это использует огромное количество оперативной памяти, что приводит к поломке моего компьютера.Используя переназначенный файл списка ребер, с которым я использовал networkitG = networkit.readGraph("edges-contig.txt", networkit.Format.EdgeListSpaceOne), Это также работает с использованием менее 4 ГБ, которые нужны играфу. networkit также поставляется с функцией для записи файлов Matlab (это форма разреженной матрицы смежности, которую может прочитать scipy). тем не мениеnetworkit.graphio.writeMat(G,"test.mat") использует огромное количество оперативной памяти, которая сбивает мой компьютер.

Наконец, ответ Саша ниже завершен, но занимает около 40 минут.