как ускорить вычисление?

Question

Мне нужно вычислить 1 миллион * 1 миллион вычислений, чтобы заполнить разреженную матрицу. Но когда я использую петли для заполнения матрицы по строкам, я нахожу, что для вычисления всего 100 * 100 потребуется всего 6 минут. задача не будет решена. Есть ли способы ускорить процесс?

import numpy as np 
from scipy.sparse import lil_matrix 
import pandas as pd 
tp = pd.read_csv('F:\\SogouDownload\\train.csv', iterator=True, chunksize=1000) 
data = pd.concat(tp, ignore_index=True) 
matrix=lil_matrix((1862220,1862220)) 
for i in range(1,1862220): 
    for j in range(1,1862220): 
     matrix[i-1,j-1]=np.sum(data[data['source_node']==i].destination_node.isin(data[data['source_node']==j].destination_node)) 

Answer 1

Хотя не самый быстрый способ построения разреженной матрицы, это не ужасно медленно либо, по крайней мере, не шаг lil назначения:

In [204]: N=100 
In [205]: M=sparse.lil_matrix((N,N)) 
In [206]: for i in range(N): 
    ...:  for j in range(N): 
    ...:   M[i,j]=(i==j) 
In [207]: M 
Out[207]: 
<100x100 sparse matrix of type '<class 'numpy.float64'>' 
    with 100 stored elements in LInked List format> 

Это спасло только ненулевые значения M. Я почти не видел задержки во время цикла.

Так что я думаю, что большая часть времени тратится в выражении panadas индексации:

np.sum(data[data['source_node']==i].destination_node.isin(data[data['source_node']==j].destination_node)) 

Преобразование данных, часто текстуального, в coocurance подсчетов разреженные матрицы часто придумывает. Они используются в обучающем коде, поиске шаблонов и т. Д. scikit-learn часто используется. Также tensorflow.

---

Для N = 1000

In [212]: %%timeit 
    ...: M=sparse.lil_matrix((N,N)) 
    ...: for i in range(N): 
    ...:  for j in range(N): 
    ...:   M[i,j]=(i==j) 
    ...: 
1 loop, best of 3: 7.31 s per loop 

Итеративно назначая эти значения в плотном массиве быстрее, даже если мы включаем преобразование в разреженной в конце.

In [213]: %%timeit 
    ...: M=np.zeros((N,N)) 
    ...: for i in range(N): 
    ...:  for j in range(N): 
    ...:   M[i,j]=(i==j) 
    ...: 
1 loop, best of 3: 353 ms per loop 

In [214]: %%timeit 
    ...: M=np.zeros((N,N)) 
    ...: for i in range(N): 
    ...:  for j in range(N): 
    ...:   M[i,j]=(i==j) 
    ...: M = sparse.lil_matrix(M) 
    ...: 
1 loop, best of 3: 353 ms per loop 

Но для очень большого случая создание промежуточного плотного массива может вызвать проблемы с памятью.

Answer 2

Техника, используемая здесь, является разреженным умножением матрицы. Но для этого метода вам сначала понадобится двоичная матрица, сопоставляющая исходные узлы с целевыми узлами (метки узлов будут индексами ненулевых записей).

from scipy.sparse import csr_matrix 

I = data['source_node'] - 1 
J = data['destination_node'] - 1 
values = np.ones(len(data), int) 
shape = (np.max(I) + 1, np.max(J) + 1) 
mapping = csr_matrix((values, (I, J)), shape) 

Сама техника просто матрица умножения этой матрицы с транспонированной (см также this question).

cooccurrence = mapping.dot(mapping.T) 

Единственная потенциальная проблема заключается в том, что результирующая матрица не может быть разреженным и потребляет всю вашу оперативную память.