Wie beschleunigt man numpy dot product mit Masken?

Question

Ich habe 2 numpy Arrays, m1 und m2 wo m1 Größe (nx1) und m2 ist Größe (1 × N) und ich möchte das Multiplikations m1.dot(m2) was in einer Matrix m der Größe (nxn)

Ich möchte, durchzuführen, um Berechnen Sie ungefähr m_approx, indem Sie nur die höchsten k Elemente in m1 und m2 verwenden und alle anderen Elemente 0 machen (alle Elemente sind positiv).

Ich versuche, die Multiplikation zu beschleunigen, weil die Größe n für mich groß ist (~ 10k). Ich möchte eine kleine k sagen 100 und wirklich die Multiplikation beschleunigen. Ich habe versucht, eine spärliche numpige Matrix zu verwenden, die das Produktprodukt viel schneller macht, aber es ist sehr langsam, m1 und m2 in spärliche Vektoren umzuwandeln. Wie kann ich das erreichen? Ich denke, Masken könnten ein Weg sein, dies zu erreichen, aber nicht sicher, wie?

Answer 1

werden Dies könnte die Indizes der größten k Elemente und np.ix_ zur Auswahl und Einstellung des Punktprodukts ausgewählter Elemente aus m1 und m2 mit np.argpartition bekommen gelöst. Wir hätten also im Grunde zwei Phasen, um dies zu implementieren, wie im Folgenden erörtert wird.

Zunächst einmal erhalten die Indizes größten k Elementen entsprechen in m1 und m2, wie so -

m1_idx = np.argpartition(-m1,k,axis=0)[:k].ravel() 
m2_idx = np.argpartition(-m2,k)[:,:k].ravel() 

Schließlich Einrichtungsausgangsarray. Verwenden Sie np.ix_, um die Indizes m1 und m2 entlang der Zeilen bzw. Spalten zu übertragen, um Elemente im Ausgangs-Array auszuwählen, die festgelegt werden sollen. bis nächstes berechnen das Skalarprodukt zwischen den höchsten k Elemente aus m1 und m2, die von m1 und m2 mit Indizierung mit m1_idx und m2_idx, wie so erhalten werden konnte -

out = np.zeros((n,n)) 
out[np.ix_(m1_idx,m2_idx)] = np.dot(m1[m1_idx],m2[:,m2_idx]) 

Lassen Sie uns die Umsetzung mit einem Probelauf überprüfen indem es gegen eine andere Implementierung ausgeführt wird, die die unteren n-k Elemente wie 0 s in m1, m2 explizit einstellt und dann das Punktprodukt ausführt. Hier ist ein Probelauf um die Prüfung auszuführen -

1) Eingänge:

In [170]: m1 
Out[170]: 
array([[ 0.26980423], 
     [ 0.30698416], 
     [ 0.60391089], 
     [ 0.73246763], 
     [ 0.35276247]]) 

In [171]: m2 
Out[171]: array([[ 0.30523552, 0.87411242, 0.01071218, 0.81835438, 0.21693231]]) 

In [172]: k = 2 

2) Führen Sie vorgeschlagene Umsetzung:

In [173]: # Proposed solution code 
    ...: m1_idx = np.argpartition(-m1,k,axis=0)[:k].ravel() 
    ...: m2_idx = np.argpartition(-m2,k)[:,:k].ravel() 
    ...: out = np.zeros((n,n)) 
    ...: out[np.ix_(m1_idx,m2_idx)] = np.dot(m1[m1_idx],m2[:,m2_idx]) 
    ...: 

3) Verwenden Sie alternative Implementierung der Ausgabe zu erhalten:

In [174]: # Explicit setting of lower n-k elements to zeros for m1 and m2 
    ...: m1[np.argpartition(-m1,k,axis=0)[k:]] = 0 
    ...: m2[:,np.argpartition(-m2,k)[:,k:].ravel()] = 0 
    ...: 

In [175]: m1 # Verify m1 and m2 have lower n-k elements set to 0s 
Out[175]: 
array([[ 0.  ], 
     [ 0.  ], 
     [ 0.60391089], 
     [ 0.73246763], 
     [ 0.  ]]) 

In [176]: m2 
Out[176]: array([[ 0.  , 0.87411242, 0.  , 0.81835438, 0.  ]]) 

In [177]: m1.dot(m2) # Use m1.dot(m2) to directly get output. This is expensive. 
Out[177]: 
array([[ 0.  , 0.  , 0.  , 0.  , 0.  ], 
     [ 0.  , 0.  , 0.  , 0.  , 0.  ], 
     [ 0.  , 0.52788601, 0.  , 0.49421312, 0.  ], 
     [ 0.  , 0.64025905, 0.  , 0.59941809, 0.  ], 
     [ 0.  , 0.  , 0.  , 0.  , 0.  ]]) 

4) Überprüfen Sie unsere vorgeschlagene Implementierung:

In [178]: out # Print output from proposed solution obtained earlier 
Out[178]: 
array([[ 0.  , 0.  , 0.  , 0.  , 0.  ], 
     [ 0.  , 0.  , 0.  , 0.  , 0.  ], 
     [ 0.  , 0.52788601, 0.  , 0.49421312, 0.  ], 
     [ 0.  , 0.64025905, 0.  , 0.59941809, 0.  ], 
     [ 0.  , 0.  , 0.  , 0.  , 0.  ]])