我有一个 1.2GB 的文本文件中图形的边列表。我的 ubuntu PC 有 8GB 内存。输入中的每一行看起来像

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)

问题是 pandas dataframe 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|是顶点的总数。这应该保存导入边列表的代码，而不必构建映射顶点名称的表。我尝试使用它:

1. 使用这个新的重新映射的边缘列表文件，我再次使用 igraph 和 g = Graph.Read_Edgelist("edges-contig.txt")。虽然它需要 4GB 的 RAM(这比它应该的理论数量多得多)，但现在可以工作了。但是，没有 igraph 函数可以从图中写出稀疏邻接矩阵。推荐的解决方案是convert the graph to a coo_matrix .不幸的是，这会占用大量 RAM，导致我的计算机崩溃。
2. 使用重新映射的边列表文件，我将 networkit 与 G = networkit.readGraph("edges-contig.txt", networkit.Format.EdgeListSpaceOne) 结合使用。这也适用于 igraph 所需的小于 4GB 的内存。 networkit 还附带了一个函数来编写 Matlab 文件(这是一种 scipy 可以读取的稀疏邻接矩阵形式)。然而 networkit.graphio.writeMat(G,"test.mat") 使用了大量的 RAM 导致我的电脑崩溃。

最后 sascha 在下面的回答确实完成了，但需要大约 40 分钟。

最佳答案

这是我的解决方案:

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

Pandas 使用 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。

请注意，一旦您将“edges.txt”转换为 CSR 矩阵格式的“edges.npz”，加载它只需不到一秒钟。

关于python - 将 1.2GB 的边列表转换为稀疏矩阵，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38688062/