Быстрое построение очень большой разреженной матрицы

Question

Как ускорить построение очень большой разреженной матрицы, где каждая строка имеет только один ненулевой элемент в соответствии с столбцом, и каждый столбец имеет равное число (в среднем) ненулевых элементов?

У меня есть огромная (разреженная) матрица размера N1 матрицы с размерностью N2, скажем, например, размера 1e85e4, матрица с размерностью, где каждая строка содержит только один ненулевой элемент, который случайным образ выбирается без замены на numpy.random.choice(numpy.arange(N2),size=N2,replace=False).

Насколько я знаю, единственный способ построить матрицу - запустить numpy.random.choice() в цикле forN1 раз. Как N1 очень большой, чтобы ускорить процесс, я использую scipy.weave:

import numpy as np 
from scipy import weave 
from scipy.weave import converters 
import scipy.sparse as sparse # Cython import 

def weave_sparse(N1,N2,w): 
    conn_matrix = sparse.dok_matrix((N1,N2)) 
    fac = lambda N : np.random.choice(np.arange(N), size=N, replace=False)[0] 
    code = """ 
      int i; 
      py::tuple arg(1); 
      arg[0] = N2; 
      for(i=0;i<N1;i++) conn_matrix[i,(int) fac.call(arg)] = w; 
      """ 
    weave.inline(code,['conn_matrix','N1','N2', 'w', 'fac'], 
       compiler='gcc',extra_compile_args=['-std=c++11 -Ofast'],force=0) 
    return conn_matrix 

Тем не менее, для N1 приближается 1e6 и за его пределами кода он занимает слишком много времени, чтобы закончить. Я подозреваю, что может быть гораздо более эффективный способ построения разреженной матрицы. Любая другая стратегия в виду, чтобы ускорить и построить матрицу в удобное для человека время?

Answer 1

Вам не нужно weave, чтобы сделать это эффективным. Вот пример, который должен сработать для вас. Я использовал небольшие значения N1 и N2, чтобы было легко проверить результат. Я также использовал csr_matrix, но любой из скудных разреженных матричных типов должен работать с небольшими изменениями или без изменений.

In [50]: from scipy.sparse import csr_matrix 

N1, N2 и массив w в основном входы; w - массив длиной N1. Он содержит значения, которые будут помещены в каждую строку. Здесь, я заполняю w с 1.

In [51]: N1 = 15 

In [52]: N2 = 12 

In [53]: w = np.empty(N1, dtype=int) 

In [54]: w[:] = 1 

Теперь создать csr_matrix:

In [55]: rows = np.arange(N1) 

In [56]: cols = np.random.randint(0, N2, size=N1) 

In [57]: conn_matrix = csr_matrix((w, (rows, cols)), shape=(N1, N2), dtype=int) 

Атрибут .A это просто ярлык для метода .toarray(); он возвращает регулярное Numpy массива:

In [58]: conn_matrix.A 
Out[58]: 
array([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], 
     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]], dtype=int64) 

Answer 2

Таким образом, проблема скорости здесь может быть переделана в качестве эффективной задачи построения очень большой разреженной матрицы. Поскольку @Warren указал np.random.choice(np.arange(N2),size=N2,replace=False) по всем N1, элементы по-прежнему являются случайной проблемой перестановки. Итак, после того, как некоторые мысли, краткая реализация для выше, может в конечном счете быть следующий:

N1 = 10000000 #1e8 
N2 = 5000 
rows = np.arange(N1) 
cols = (np.floor(np.random.permutation(N1)/float(N1)*N2)).astype(int) # Randomly pick N1 objects and assign to N2 categories in almost equal proportion 
w = np.ones(N1) 
conn_matrix = sparse.csr_matrix((w, (rows, cols)), shape=(N1, N2), dtype=int)