Schneller Aufbau einer sehr großen spärlichen Matrix

Question

Wie kann man die Konstruktion einer sehr großen dünn besetzten Matrix beschleunigen, in der jede Zeile nur ein Element ungleich null in einer Spalte hat und jede Spalte eine gleiche Anzahl (im Durchschnitt) von null Elementen hat?

I eine riesige (sparse) Matrix der Größe N1 -by- N2, sagen wir beispielsweise der Größe 1e8 -by- 5e4, wobei jede Zeile enthält nur ein Nicht-Null-Element haben, die zufällig ohne Ersatz durch numpy.random.choice(numpy.arange(N2),size=N2,replace=False) gewählt wird.

Soweit ich weiß, ist der einzige Weg, wie ich die Matrix bauen kann, numpy.random.choice() in einer for Schleife N1 mal zu laufen. Als N1 sehr groß ist, die Dinge zu beschleunigen Ich bin mit 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 

Noch für N11e6 nähern und über den Code abzuschließen es zu lange dauert. Ich vermute, dass es einen viel effizienteren Weg zum Aufbau der Sparse-Matrix geben könnte. Irgendeine andere Strategie, um die Matrix in einer für Menschen lesbaren Zeit zu beschleunigen und aufzubauen?

Answer 1

Sie sollten weave nicht benötigen, um dies effizient zu machen. Hier ist ein Beispiel, das für Sie arbeiten sollte. Ich verwendete kleine Werte von N1 und N2, um es einfach zu machen, das Ergebnis zu überprüfen. Ich benutzte auch csr_matrix, aber jeder der scipy Sparse-Matrix-Typen sollte mit wenig oder keine Änderungen funktionieren.

In [50]: from scipy.sparse import csr_matrix 

N1, N2 und das Array w sind im Grunde die Eingänge; w ist ein Array der Länge N1. Es enthält die Werte, die in jeder Zeile stehen. Hier, ich füllen w mit 1.

In [51]: N1 = 15 

In [52]: N2 = 12 

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

In [54]: w[:] = 1 

Erstellen Sie nun die 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) 

Das .A Attribut ist nur eine Abkürzung für die .toarray() Methode; es gibt eine regelmäßige numpy Array:

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

So, hier das Geschwindigkeitsproblem als ein effizientes Problem des Aufbaus der sehr große Sparse Matrix neu gefasst werden kann. Als @Warren wies np.random.choice(np.arange(N2),size=N2,replace=False) über alle N1 Elemente ist immer noch ein zufälliges Permutationsproblem. So, nach einigen Gedanken, eine kurze Einführung für die oben könnte letztlich die folgende sein:

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)