Code Optimierung - Anzahl der Funktionsaufrufe in Python

Question

Ich würde gerne wissen, wie ich dieses Problem umwandeln könnte, um den Overhead der np.sum() Funktionsaufrufe in meinem Code zu reduzieren.

Ich habe eine input Matrix, sagen wir von shape=(1000, 36). Jede Zeile repräsentiert einen Knoten in einem Diagramm. Ich habe eine Operation, die ich mache, die über jede Zeile iteriert und eine elementweise Addition zu einer variablen Anzahl anderer Zeilen ausführt. Diese "anderen" Zeilen sind in einem Verzeichnis nodes_nbrs definiert, das für jede Zeile eine Liste von Zeilen aufzeichnet, die zusammen summiert werden müssen. Ein Beispiel dafür ist als solche:

nodes_nbrs = {0: [0, 1], 
       1: [1, 0, 2], 
       2: [2, 1], 
       ...} 

Hier Knoten 0 in die Summe von Knoten transformiert werden würde und 01. Der Knoten 1 würde in die Summe der Knoten 1, 0 und 2 umgewandelt werden. Und so weiter für den Rest der Knoten.

Die aktuelle (und naive) Art, die ich derzeit implementiert habe, ist als solche. Ich zum ersten Mal eines Null-Array der endgültigen Form instanziiert, die ich will, und dann im nodes_nbrs Wörterbuch über jeden Schlüssel-Wert-Paar iterieren:

output = np.zeros(shape=input.shape) 
for k, v in nodes_nbrs.items(): 
    output[k] = np.sum(input[v], axis=0) 

Dieser Code ist alles kühl und fein in kleinen Tests (shape=(1000, 36)), aber Bei größeren Tests (shape=(~1E(5-6), 36)) dauert es ~ 2-3 Sekunden. Ich muss diese Operation tausendmal durchführen, also versuche ich, ob es einen optimierten Weg gibt.

Nachdem ich Linienprofilierung gemacht habe, habe ich festgestellt, dass der Schlüsselkiller hier die np.sum Funktion immer und immer wieder aufruft, was etwa 50% der Gesamtzeit beansprucht. Gibt es eine Möglichkeit, diesen Overhead zu eliminieren? Oder gibt es eine andere Möglichkeit, dies zu optimieren?

---

aus, dass Apart, hier ist eine Liste der Dinge, die ich getan habe, und (sehr kurz) ihre Ergebnisse:

• A cython Version: entfällt die for Art Schleife Kopf Überprüfung, 30% Ermäßigung in der Zeit genommen. Bei der cython-Version benötigt np.sum etwa 80% der gesamten Wanduhrzeit statt 50%.
• Deklarieren Sie np.sum als Variable npsum, und rufen Sie npsum innerhalb der for Schleife. Kein Unterschied zum Original.
• Ersetzen np.sum mit np.add.reduce, und daß an die Variable npsum, zuweisen und dann im Inneren des npsumfor Schleife aufzurufen. ~ 10% Reduzierung der Wanduhrzeit, aber dann inkompatibel mit autograd (Erklärung unten in spärlichen Matrizen Aufzählungspunkt).
• numba JIT-ing: nicht mehr als das Hinzufügen von Decorator versucht. Keine Verbesserung, aber ich habe mich nicht angestrengt.
• Konvertieren Sie das nodes_nbrs Wörterbuch in ein dichtes numpy Binärarray (1s und 0s), und führen Sie dann eine einzelne np.dot Operation. Gut in der Theorie, schlecht in der Praxis, weil es eine quadratische Matrix von shape=(10^n, 10^n) erfordern würde, die in der Speichernutzung quadratisch ist.

Dinge, die ich habe nicht versucht, aber ich bin zögerlich, dies zu tun:

• scipy Sparse-Matrizen: Ich autograd verwende, die nicht automatische Differenzierung der dot Betrieb unterstützt für scipy Sparse-Matrizen.

---

Für diejenigen, die neugierig sind, ist dies im Wesentlichen eine Faltungsoperation auf die Grafik-strukturierte Daten. Irgendwie macht es Spaß, dies für die Schule zu entwickeln, aber auch etwas frustrierend, wenn man an der Spitze des Wissens ist.

Answer 1

Wenn scipy.sparse keine Option ist, könnten Sie dies zum Beispiel tun, um Ihre Daten so zu massieren, dass Sie mit vektorisierten Funktionen alles in der kompilierten Ebene ausführen können. Wenn Sie das Wörterbuch Ihrer Nachbarn in ein zweidimensionales Array mit entsprechenden Flags für fehlende Werte ändern, können Sie np.take verwenden, um die gewünschten Daten zu extrahieren, und dann einen einzelnen sum()-Aufruf ausführen.

Hier ist ein Beispiel dessen, was ich im Sinn haben:

import numpy as np 

def make_data(N=100): 
    X = np.random.randint(1, 20, (N, 36)) 
    connections = np.random.randint(2, 5, N) 
    nbrs = {i: list(np.random.choice(N, c)) 
      for i, c in enumerate(connections)} 
    return X, nbrs 

def original_solution(X, nbrs): 
    output = np.zeros(shape=X.shape) 
    for k, v in nbrs.items(): 
     output[k] = np.sum(X[v], axis=0) 
    return output 

def vectorized_solution(X, nbrs): 
    # Make neighbors all the same length, filling with -1 
    new_nbrs = np.full((X.shape[0], max(map(len, nbrs.values()))), -1, dtype=int) 
    for i, v in nbrs.items(): 
     new_nbrs[i, :len(v)] = v 

    # add a row of zeros to X 
    new_X = np.vstack([X, 0 * X[0]]) 

    # compute the sums 
    return new_X.take(new_nbrs, 0).sum(1) 

Jetzt können wir, dass die Ergebnisse übereinstimmen bestätigen:

>>> X, nbrs = make_data(100) 
>>> np.allclose(original_solution(X, nbrs), 
       vectorized_solution(X, nbrs)) 
True 

Und wir können die Dinge Zeit, um die Beschleunigung zu sehen:

X, nbrs = make_data(1000) 
%timeit original_solution(X, nbrs) 
%timeit vectorized_solution(X, nbrs) 
# 100 loops, best of 3: 13.7 ms per loop 
# 100 loops, best of 3: 1.89 ms per loop 

Nach oben zu größeren Größen:

X, nbrs = make_data(100000) 
%timeit original_solution(X, nbrs) 
%timeit vectorized_solution(X, nbrs) 
1 loop, best of 3: 1.42 s per loop 
1 loop, best of 3: 249 ms per loop 

Es geht um einen Faktor von 5-10 schneller, der für Ihre Zwecke gut genug sein kann (obwohl dies stark von den genauen Eigenschaften Ihres Wörterbuchs nbrs abhängt).

---

Edit: Just for fun, versuchte ich ein paar andere Ansätze, eine mit numpy.add.reduceat, ein pandas.groupby verwenden und ein scipy.sparse verwenden. Es scheint, dass der Vektoransatz, den ich ursprünglich vorgeschlagen habe, wahrscheinlich die beste Wahl ist. Hier sind sie als Referenz:

from itertools import chain 

def reduceat_solution(X, nbrs): 
    ind, j = np.transpose([[i, len(v)] for i, v in nbrs.items()]) 
    i = list(chain(*(nbrs[i] for i in ind))) 
    j = np.concatenate([[0], np.cumsum(j)[:-1]]) 
    return np.add.reduceat(X[i], j)[ind] 

np.allclose(original_solution(X, nbrs), 
      reduceat_solution(X, nbrs)) 
# True 

-

import pandas as pd 

def groupby_solution(X, nbrs): 
    i, j = np.transpose([[k, vi] for k, v in nbrs.items() for vi in v]) 
    return pd.groupby(pd.DataFrame(X[j]), i).sum().values 

np.allclose(original_solution(X, nbrs), 
      groupby_solution(X, nbrs)) 
# True 

-

from scipy.sparse import csr_matrix 
from itertools import chain 

def sparse_solution(X, nbrs): 
    items = (([i]*len(col), col, [1]*len(col)) for i, col in nbrs.items()) 
    rows, cols, data = (np.array(list(chain(*a))) for a in zip(*items)) 
    M = csr_matrix((data, (rows, cols))) 
    return M.dot(X) 

np.allclose(original_solution(X, nbrs), 
      sparse_solution(X, nbrs)) 
# True 

Und alle Timings zusammen:

X, nbrs = make_data(100000) 
%timeit original_solution(X, nbrs) 
%timeit vectorized_solution(X, nbrs) 
%timeit reduceat_solution(X, nbrs) 
%timeit groupby_solution(X, nbrs) 
%timeit sparse_solution(X, nbrs) 
# 1 loop, best of 3: 1.46 s per loop 
# 1 loop, best of 3: 268 ms per loop 
# 1 loop, best of 3: 416 ms per loop 
# 1 loop, best of 3: 657 ms per loop 
# 1 loop, best of 3: 282 ms per loop 

Answer 2

Basiert auf der Arbeit auf den letzten spärlichen Fragen, z.B Extremely slow sum row operation in Sparse LIL matrix in Python

Hier ist, wie Ihre Art von Problem mit dünn besetzten Matrizen gelöst werden könnte. Die Methode könnte auch für dichte Anwendungen gelten. Die Idee ist, dass spärlich sum als Matrixprodukt mit einer Zeile (oder Spalte) von 1s implementiert. Die Indizierung von dünn besetzten Matrizen ist langsam, aber das Matrixprodukt ist ein guter C-Code.

In diesem Fall werde ich eine Multiplikationsmatrix erstellen, die 1s für die Zeilen hat, die ich summieren möchte - verschiedene 1s für jeden Eintrag im Wörterbuch.

eine Probenmatrix:

In [302]: A=np.arange(8*3).reshape(8,3)  
In [303]: M=sparse.csr_matrix(A) 

Auswahl Wörterbuch:

In [304]: dict={0:[0,1],1:[1,0,2],2:[2,1],3:[3,4,7]} 

build eine Sparse-Matrix aus diesem Wörterbuch. Dies ist vielleicht nicht der effizienteste Weg, eine solche Matrix zu konstruieren, aber es reicht aus, die Idee zu demonstrieren.

In [305]: r,c,d=[],[],[] 
In [306]: for i,col in dict.items(): 
    c.extend(col) 
    r.extend([i]*len(col)) 
    d.extend([1]*len(col)) 

In [307]: r,c,d 
Out[307]: 
([0, 0, 1, 1, 1, 2, 2, 3, 3, 3], 
[0, 1, 1, 0, 2, 2, 1, 3, 4, 7], 
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) 

In [308]: idx=sparse.csr_matrix((d,(r,c)),shape=(len(dict),M.shape[0])) 

die Summe durchführen und das Ergebnis sehen (als dichtes Array):

In [310]: (idx*M).A 
Out[310]: 
array([[ 3, 5, 7], 
     [ 9, 12, 15], 
     [ 9, 11, 13], 
     [42, 45, 48]], dtype=int32) 

Hier ist das Original zum Vergleich.

In [312]: M.A 
Out[312]: 
array([[ 0, 1, 2], 
     [ 3, 4, 5], 
     [ 6, 7, 8], 
     [ 9, 10, 11], 
     [12, 13, 14], 
     [15, 16, 17], 
     [18, 19, 20], 
     [21, 22, 23]], dtype=int32)