Convertir una lista de bordes de 1.2GB en una matriz dispersa

Tengo una lista de bordes de 1.2GB de un gráfico en un archivo de texto. Mi ubuntu PC tiene 8GB de RAM. Cada línea en la entrada se ve como

287111206 357850135 

Me gustaría convertirlo en una matriz de adyacencia dispersa y enviarlo a un archivo.

Algunas estadísticas para mis datos:

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

Hice casi la misma pregunta antes en https://stackoverflow.com/a/38667644/2179021 y obtuve una gran respuesta. El problema es que no puedo hacerlo funcionar.

Primero intenté cargar np.loadtxt en el archivo, pero era muy lento y usaba una gran cantidad de memoria. Así que en lugar de eso me mudé a pandas.read_csv, que es muy rápido, pero esto causó sus propios problemas. Este es mi código actual:

 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) 

El problema es que los data marco de data pandas son enormes y efectivamente estoy haciendo una copia en A que es ineficiente. Sin embargo, las cosas son aún peores, ya que el código falla

  Traceback (most recent call last): File "make-sparse-matrix.py", line 13, in  rows,cols=k3.reshape(A.shape).T AttributeError: 'function' object has no attribute 'shape' raph@raph-desktop:~/python$ python make-sparse-matrix.py  Traceback (most recent call last): File "make-sparse-matrix.py", line 12, in  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 

Así que mis preguntas son:

  1. ¿Puedo evitar tener en la memoria tanto el dataframe pandas de 1.2GB como la matriz numpy de 1.2GB?
  2. ¿Hay alguna manera de hacer que el código se complete en 8GB de RAM?

Puede reproducir una entrada de prueba del tamaño que estoy tratando de procesar con:

 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 

Actualizar

Ahora he intentado una serie de enfoques diferentes, todos los cuales han fracasado. Aquí hay un resumen.

  1. Usando igraph con g = Graph.Read_Ncol('edges.txt') . Esto utiliza una gran cantidad de RAM que bloquea mi computadora.
  2. Utilizando networkit con G= networkit.graphio.readGraph("edges.txt", networkit.Format.EdgeList, separator=" ", continuous=False) . Esto utiliza una gran cantidad de RAM que bloquea mi computadora.
  3. El código de arriba en esta pregunta pero utilizando np.loadtxt (“edges.txt”) en lugar de pandas. Esto utiliza una gran cantidad de RAM que bloquea mi computadora.

Luego escribí un código separado que reasignó todos los nombres de vértices al número de 1 … | V | donde | V | es el número total de vértices. Esto debería guardar el código que importa la lista de borde de tener que construir una tabla que asigna los nombres de vértice. Usando esto intenté:

  1. Usando este nuevo archivo de lista de bordes reasignados, utilicé igraph nuevamente con g = Graph.Read_Edgelist("edges-contig.txt") . Esto ahora funciona aunque toma 4 GB de RAM (que es mucho más que la cantidad teórica que debería). Sin embargo, no hay una función igraph para escribir una matriz de adyacencia dispersa de un gráfico. La solución recomendada es convertir el gráfico a una coo_matrix . Desafortunadamente, esto utiliza una gran cantidad de RAM que bloquea mi computadora.
  2. Usando el archivo de la lista de bordes reasignados, utilicé networkit con G = networkit.readGraph("edges-contig.txt", networkit.Format.EdgeListSpaceOne) . Esto también funciona con menos de los 4 GB que necesita igraph. networkit también viene con una función para escribir archivos Matlab (que es una forma de matriz de adyacencia dispersa que scipy puede leer). Sin embargo, networkit.graphio.writeMat(G,"test.mat") usa una gran cantidad de RAM que bloquea mi computadora.

Finalmente, la respuesta de sascha a continuación se completa pero toma alrededor de 40 minutos.

Aquí está mi solución:

 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 hace el trabajo pesado de analizar usando read_csv . Y Pandas ya está almacenando los datos en formato de columnas. Los data[0] y los data[1] solo obtienen referencias, no hay copias. Luego los alimento a coo_matrix . Bencheado localmente:

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

Luego, para guardar una matriz csr en un archivo:

 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) 

Bencheado localmente:

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

Y luego volver a cargarlo desde un archivo:

 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 

Bencheado localmente:

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

Y finalmente probarlo todo:

 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() 

Cuando se ejecuta la test() , toma alrededor de 30 segundos:

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

Y la marca de límite superior de memoria era ~ 1.79 GB.

Tenga en cuenta que una vez que haya convertido “edges.txt” a “edges.npz” en formato de matriz CSR, cargarlo tomará menos de un segundo.

Versión actualizada

Como se indica en los comentarios, el enfoque no se ajustó a su caso de uso. Vamos a hacer algunos cambios:

  • use pandas para leer los datos (en lugar de numpy: estoy bastante sorprendido de que np.loadtxt se esté desempeñando tan mal)
  • use los clasificadores externos de la biblioteca para un enfoque más eficiente de la memoria (en lugar de un diccionario)
  • El enfoque básico es el mismo.

Este enfoque tomará ~ 45 minutos (lo que es lento; pero puede hacer un pickle / guardar el resultado, por lo que necesita hacerlo solo una vez ) y ~ 5 GB de memoria para preparar la matriz dispersa para sus datos, generada con:

 import random N = 62500000 for i in xrange(N): print random.randint(10**8,10**9-1), random.randint(10**8,10**9-1) 

Código

 import numpy as np from scipy.sparse import coo_matrix import pandas as pd from sortedcontainers import SortedList import time # Read data # global memory usage after: one big array df = pd.read_csv('EDGES.txt', delimiter=' ', header=None, dtype=np.uint32) data = df.as_matrix() df = None n_edges = data.shape[0] # Learn mapping to range(0, N_VERTICES) # N_VERTICES unknown # global memory usage after: one big array + one big searchtree print('fit mapping') start = time.time() observed_vertices = SortedList() mappings = np.arange(n_edges*2, dtype=np.uint32) # upper bound on vertices for column in range(data.shape[1]): for row in range(data.shape[0]): # double-loop: slow, but easy to understand space-complexity val = data[row, column] if val not in observed_vertices: observed_vertices.add(val) mappings = mappings[:len(observed_vertices)] n_vertices = len(observed_vertices) end = time.time() print(' secs: ', end-start) print('transform mapping') # Map original data (in-place !) # global memory usage after: one big array + one big searchtree(can be deleted!) start = time.time() for column in range(data.shape[1]): for row in range(data.shape[0]): # double-loop: slow, but easy to understand space-complexity val = data[row, column] mapper_pos = observed_vertices.index(val) data[row, column] = mappings[mapper_pos] end = time.time() print(' secs: ', end-start) observed_vertices = None # if not needed anymore mappings = None # if not needed anymore # Create sparse matrix (only caring about a single triangular part for now) # if needed: delete dictionary before as it's not needed anymore! sp_mat = coo_matrix((np.ones(n_edges, dtype=bool), (data[:, 0], data[:, 1])), shape=(n_vertices, n_vertices)) 

Primera versión

Aquí hay un código muy simple y muy ineficiente (en lo que respecta al tiempo y al espacio) para construir esta matriz dispersa. Publico este código, porque creo que es importante entender las partes principales si uno las está usando en algo más grande.

Veamos si este código es lo suficientemente eficiente para su caso de uso o si necesita trabajo. Desde la distancia es difícil saberlo, porque no tenemos sus datos.

La parte del diccionario, utilizada para el mapeo, es una candidata para volar tu memoria. Pero no tiene sentido optimizar esto sin saber si es necesario. Especialmente porque esta parte del código depende de la cantidad de vértices en su gráfica (y no tengo ningún conocimiento de esta cardinalidad).

 """ itertools.count usage here would need changes for py2 """ import numpy as np from itertools import count from scipy.sparse import coo_matrix # Read data # global memory usage after: one big array data = np.loadtxt('edges.txt', np.uint32) n_edges = data.shape[0] #print(data) #print(data.shape) # Learn mapping to range(0, N_VERTICES) # N_VERTICES unknown # global memory usage after: one big array + one big dict index_gen = count() mapper = {} for column in range(data.shape[1]): for row in range(data.shape[0]): # double-loop: slow, but easy to understand space-complexity val = data[row, column] if val not in mapper: mapper[val] = next(index_gen) n_vertices = len(mapper) # Map original data (in-place !) # global memory usage after: one big array + one big dict (can be deleted!) for column in range(data.shape[1]): for row in range(data.shape[0]): # double-loop: slow, but easy to understand space-complexity data[row, column] = mapper[data[row, column]] #print(data) # Create sparse matrix (only caring about a single triangular part for now) # if needed: delete dictionary before as it's not needed anymore! sp_mat = coo_matrix((np.ones(n_edges, dtype=bool), (data[:, 0], data[:, 1])), shape=(n_vertices, n_vertices)) #print(sp_mat) 

Salida para bordes-10.txt :

 [[287111206 357850135] [512616930 441657273] [530905858 562056765] [524113870 320749289] [149911066 964526673] [169873523 631128793] [646151040 986572427] [105290138 382302570] [194873438 968653053] [912211115 195436728]] (10, 2) [[ 0 10] [ 1 11] [ 2 12] [ 3 13] [ 4 14] [ 5 15] [ 6 16] [ 7 17] [ 8 18] [ 9 19]] (0, 10) True (1, 11) True (2, 12) True (3, 13) True (4, 14) True (5, 15) True (6, 16) True (7, 17) True (8, 18) True (9, 19) True 

Estaba probando los diferentes métodos disponibles, aparte de los que ya se usaban. Encontré lo siguiente bien.

Método 1: leer el archivo en una cadena, analizar la cadena en una matriz 1-D usando la cadena de caracteres de numpy.

 import numpy as np import scipy.sparse as sparse def readEdges(): with open('edges.txt') as f: data = f.read() edges = np.fromstring(data, dtype=np.int32, sep=' ') edges = np.reshape(edges, (edges.shape[0]/2, 2)) ones = np.ones(len(edges), np.uint32) cooMatrix = sparse.coo_matrix((ones, (edges[:,0], edges[:,1]))) %timeit -n5 readEdges() 

Salida:

 5 loops, best of 3: 13.6 s per loop 

Método 2: igual que el método 1, excepto en lugar de cargar el archivo en una cadena, utilizando la interfaz de memoria asignada.

 def readEdgesMmap(): with open('edges.txt') as f: with contextlib.closing(mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)) as m: edges = np.fromstring(m, dtype=np.int32, sep=' ') edges = np.reshape(edges, (edges.shape[0]/2, 2)) ones = np.ones(len(edges), np.uint32) cooMatrix = sparse.coo_matrix((ones, (edges[:,0], edges[:,1]))) %timeit -n5 readEdgesMmap() 

Salida:

 5 loops, best of 3: 12.7 s per loop 

Supervisado con /usr/bin/time , ambos métodos utilizan un máximo de ~ 2GB de memoria.

Algunas notas:

  1. Parece hacerlo un poco mejor que los pandas read_csv . Usando pandas read_csv, la salida en la misma máquina es

    5 loops, best of 3: 16.2 s per loop

  2. La conversión de COO a CSR / CSC también consume mucho tiempo. En la respuesta de @ GrantJ, lleva menos tiempo porque la inicialización de la matriz de COO es incorrecta. El argumento debe ser dado como una tupla. Quería dejar un comentario allí pero todavía no tengo derechos para comentar.

  3. Mi conjetura sobre por qué esto es ligeramente mejor que los pandas read_csv es la suposición previa de los datos 1D.

En mi respuesta, considero el caso en el que las identificaciones de los nodos están dadas por 9 caracteres cadenas largas cada carácter de [0-9A-Za-z] . n de estos identificadores de nodo deben asignarse a los valores [0,n-1] (lo que podría no ser necesario para su aplicación, pero aún de interés general).

Las siguientes consideraciones, estoy seguro de que están al tanto, están aquí para completarlas:

  1. La memoria es el cuello de la botella.
  2. Hay alrededor de 10^8 cadenas en el archivo.
  3. un par de string + int32 9 caracteres string + int32 valor string + int32 cuesta alrededor de 120 bytes en un diccionario, lo que resulta en un uso de memoria de 12GB para el archivo.
  4. un id de cadena del archivo se puede asignar a un int64 : hay 62 caracteres diferentes -> se pueden codificar con 6 bits, 9 caracteres en la cadena -> 6 * 9 = 54 <64 bits. Vea también el método toInt64() más abajo.
  5. hay int64 + int32 = 12 bytes de información “real” => ca. 1.2 GB podría ser suficiente, sin embargo, el costo de tal par en un diccionario es de alrededor de 60 bytes (se necesitan alrededor de 6 GB de RAM).
  6. La creación de objetos pequeños (en el montón) produce una gran sobrecarga de memoria, por lo que es ventajoso agrupar estos objetos en arreglos. Se puede encontrar información interesante sobre la memoria utilizada por los objetos de Python en este artículo de tutorial. Las experiencias interesantes con la reducción del uso de la memoria se hacen públicas en esta entrada de blog .
  7. python-list está fuera de discusión como estructura de datos y como diccionario. array.array podría ser una alternativa, pero usamos np.array (porque hay algoritmos de clasificación para np.array pero no array.array ).

1. paso: leer el archivo y asignar cadenas a int64 . Es un dolor dejar que np.array crezca dinámicamente, por lo que asumimos que ahora tenemos el número de bordes en el archivo (sería bueno tenerlo en el encabezado, pero también puede deducirse del tamaño del archivo):

 import numpy as np def read_nodes(filename, EDGE_CNT): nodes=np.zeros(EDGE_CNT*2, dtype=np.int64) cnt=0 for line in open(filename,"r"): nodes[cnt:cnt+2]=map(toInt64, line.split()) # use map(int, line.split()) for cases without letters return nodes 

2. paso: convertir los valores de int64 en valores [0,n-1] :

Posibilidad A , necesita 3 * 0.8GB:

 def maps_to_ids(filename, EDGE_CNT): """ return number of different node ids, and the mapped nodes""" nodes=read_nodes(filename, EDGE_CNT) unique_ids, nodes = np.unique(nodes, return_index=True) return (len(unique_ids), nodes) 

Posibilidad B , necesita 2 * 0.8GB, pero es algo más lento:

 def maps_to_ids(filename, EDGE_CNT): """ return number of different node ids, and the mapped nodes""" nodes=read_nodes(filename, EDGE_CNT) unique_map = np.unique(nodes) for i in xrange(len(nodes)): node_id=np.searchsorted(unique_map, nodes[i]) # faster than bisect.bisect nodes[i]=node_id return (len(unique_map), nodes) 

3. paso: ponlo todo en coo_matrix:

 from scipy import sparse def data_as_coo_matrix(filename, EDGE_CNT) node_cnt, nodes = maps_to_ids(filename, EDGE_CNT) rows=nodes[::2]#it is only a view, not a copy cols=nodes[1::2]#it is only a view, not a copy return sparse.coo_matrix((np.ones(len(rows), dtype=bool), (rows, cols)), shape=(node_cnt, node_cnt)) 

Para llamar a data_as_coo_matrix("data.txt", 62500000) , la memoria necesita picos a 2.5GB (pero con int32 lugar de int64 solo se necesitan 1.5GB). Tomó alrededor de 5 minutos en mi máquina, pero mi máquina es bastante lenta …

Entonces, ¿qué es diferente de su solución?

  1. Solo obtengo valores únicos de np.unique (y no todos los índices y el inverso), así que hay algo de memoria guardada. Puedo reemplazar las antiguas identificaciones con las nuevas in situ.
  2. No tengo experiencia con pandas así que tal vez haya algo de copia involucrada entre pandas <-> numpy estructuras de datos.

¿Cuál es la diferencia con la solución de sascha?

  1. No hay necesidad de ordenar la lista todo el tiempo; es suficiente ordenar una vez que todos los elementos están en la lista, eso es lo que hace np.unique() . La solución de sascha mantiene la lista ordenada todo el tiempo. Debe pagar por esto con al menos un factor constante, incluso si el tiempo de ejecución sigue siendo O(n log(n)) . Supuse que una operación de adición sería O(n) , pero como se señaló, es O(log(n) .

¿Cuál es la diferencia con la solución de GrantJ?

  1. El tamaño de la matriz dispersa resultante es NxN – con N – número de nodos diferentes y no 2^54x2^54 (con muchas filas y columnas vacías).

PD:
Aquí está mi idea, cómo se puede asignar la identificación de cadena de 9 caracteres en un valor int64 , pero creo que esta función podría convertirse en un cuello de botella de la forma en que está escrita y debería optimizarse.

 def toInt64(string): res=0L for ch in string: res*=62 if ch <='9': res+=ord(ch)-ord('0') elif ch <='Z': res+=ord(ch)-ord('A')+10 else: res+=ord(ch)-ord('a')+36 return res 

Es posible que desee echar un vistazo al proyecto igraph , esta es una biblioteca GPL de código C que está diseñada para este tipo de cosas y tiene una buena API de Python. Creo que en tu caso el código Python sería algo así como

 from igraph import Graph g = Graph.Read_Edgelist('edges.txt') g.write_adjacency('adjacency_matrix.txt')