将1.2GB边的列表转换为稀疏矩阵

Question

我在文本文件中有一个1.2GB的边缘列表.我的ubuntu PC有8GB的RAM.输入中的每一行都是如此

287111206 357850135

我想将其转换为稀疏邻接矩阵并将其输出到文件.

我的数据的一些统计数据:

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

我之前在/sf/answers/2706735111/问了很多相同的问题并得到了很好的答案.问题是我无法让它发挥作用.

我首先尝试使用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)

问题是pandas数据框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. 我可以避免在内存中同时拥有1.2GB的pandas数据帧和1.2GB numpy数组吗？
2. 有没有办法让代码在8GB内存中完成？

您可以重现我尝试处理的大小的测试输入:

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

更新

我现在尝试了许多不同的方法,所有方法都失败了.这是一个总结.

1. 使用igraph与g = Graph.Read_Ncol('edges.txt').这使用了大量的RAM,导致我的计算机崩溃.
2. 使用networkit用G= networkit.graphio.readGraph("edges.txt", networkit.Format.EdgeList, separator=" ", continuous=False).这使用了大量的RAM,导致我的计算机崩溃.
3. 这个问题上面的代码,但使用np.loadtxt("edges.txt")而不是pandas.这使用了大量的RAM,导致我的计算机崩溃.

然后我编写了单独的代码,将所有顶点名称重新映射为1 ... | V |中的数字 其中| V | 是顶点的总数.这应该保存导入边列表的代码,使其不必构建映射顶点名称的表.用这个我试过:

4. 使用这个新的重新映射的边缘列表文件我再次使用igraph g = Graph.Read_Edgelist("edges-contig.txt").这现在可以工作,虽然它需要4GB的RAM(这远远超过它应该的理论量).但是,没有igraph函数从图形中写出稀疏邻接矩阵.建议的解决方案是将图形转换为coo_matrix.不幸的是,这会占用大量RAM,导致我的计算机崩溃.
5. 使用重新映射的边缘列表文件我使用networkit G = networkit.readGraph("edges-contig.txt", networkit.Format.EdgeListSpaceOne).这也可以使用低于igraph需要的4GB.networkit还附带了编写Matlab文件的函数(这是scipy可以读取的稀疏邻接矩阵的一种形式).然而,networkit.graphio.writeMat(G,"test.mat")使用大量的RAM会导致我的计算机崩溃.

最后,sascha的答案确实完成,但大约需要40分钟.

Answer 1

这是我的解决方案:

import numpy as np
import pandas as pd
import scipy.sparse as ss

def read_data_file_as_coo_matrix(filename='edges.txt'):
    "Read data file and return sparse matrix in coordinate format."
    data = pd.read_csv(filename, sep=' ', header=None, dtype=np.uint32)
    rows = data[0]  # Not a copy, just a reference.
    cols = data[1]
    ones = np.ones(len(rows), np.uint32)
    matrix = ss.coo_matrix((ones, (rows, cols)))
    return matrix

熊猫用解决方法解决了繁重的问题read_csv.而且Pandas已经以列式格式存储数据.在data[0]与data[1]刚刚获得引用,无份.然后我喂那些coo_matrix.本地基准:

In [1]: %timeit -n1 -r5 read_data_file_as_coo_matrix()
1 loop, best of 5: 14.2 s per loop

然后将csr矩阵保存到文件中:

def save_csr_matrix(filename, matrix):
    """Save compressed sparse row (csr) matrix to file.

    Based on http://stackoverflow.com/a/8980156/232571

    """
    assert filename.endswith('.npz')
    attributes = {
        'data': matrix.data,
        'indices': matrix.indices,
        'indptr': matrix.indptr,
        'shape': matrix.shape,
    }
    np.savez(filename, **attributes)

本地基准:

In [3]: %timeit -n1 -r5 save_csr_matrix('edges.npz', matrix.tocsr())
1 loop, best of 5: 13.4 s per loop

然后从文件中加载它:

def load_csr_matrix(filename):
    """Load compressed sparse row (csr) matrix from file.

    Based on http://stackoverflow.com/a/8980156/232571

    """
    assert filename.endswith('.npz')
    loader = np.load(filename)
    args = (loader['data'], loader['indices'], loader['indptr'])
    matrix = ss.csr_matrix(args, shape=loader['shape'])
    return matrix

本地基准:

In [4]: %timeit -n1 -r5 load_csr_matrix('edges.npz')
1 loop, best of 5: 881 ms per loop

最后测试一下:

def test():
    "Test data file parsing and matrix serialization."
    coo_matrix = read_data_file_as_coo_matrix()
    csr_matrix = coo_matrix.tocsr()
    save_csr_matrix('edges.npz', csr_matrix)
    loaded_csr_matrix = load_csr_matrix('edges.npz')
    # Comparison based on http://stackoverflow.com/a/30685839/232571
    assert (csr_matrix != loaded_csr_matrix).nnz == 0

if __name__ == '__main__':
    test()

运行时test(),大约需要30秒:

$ time python so_38688062.py 
real    0m30.401s
user    0m27.257s
sys     0m2.759s

记忆高水位标记约为1.79 GB.

请注意,一旦您以CSR矩阵格式将"edges.txt"转换为"edges.npz",加载它将花费不到一秒钟.