Wie effiziente Vektorisierung in numpy durchzuführen (Speicherbeschränkungen)

Question

Ich habe mit vielen Daten zu tun, gespeichert in einem np.array der Größe (3, n).

Ich muss für jedes Datum x: xx.T durchführen (um eine 3x3-Matrix zu bilden). Das würde also viele 3x3-Matrizen ergeben. Ich muss dann die Ergebnisse jeder dieser Matrizen addieren, um eine Gesamt 3x3-Matrix zu bilden.

Ich tat dies wie folgt: np.einsum('ij,ki->jk', x, x.T), die zu funktionieren scheint. Aber das Problem ist, mein n ist unglaublich groß (ich habe es mit sehr großen Bildern von vielen Megapixeln zu tun), und diese Methode ergibt eine MemoryError.

Gibt es noch andere Möglichkeiten, dies unter Beibehaltung einer vektorisierten Methode zu erreichen?

Danke!

Answer 1

aus Ihrem Kommentar Arbeiten:

In [465]: x=np.array([[1,2,3],[4,5,6]]) 
In [466]: np.einsum('ij,ik', x,x) 
Out[466]: 
array([[17, 22, 27], 
     [22, 29, 36], 
     [27, 36, 45]]) 
In [467]: x=np.ones((10,3)) 
In [468]: np.einsum('ij,ik', x,x) 
Out[468]: 
array([[ 10., 10., 10.], 
     [ 10., 10., 10.], 
     [ 10., 10., 10.]]) 
In [471]: x=np.ones((10000000,3)) 
In [472]: np.einsum('ij,ik', x,x) 
Out[472]: 
array([[ 10000000., 10000000., 10000000.], 
     [ 10000000., 10000000., 10000000.], 
     [ 10000000., 10000000., 10000000.]]) 

Wenn das Array für Speicher zu groß wird, können Sie es versuchen Chunking:

In [479]: res = np.zeros((3,3)) 
In [480]: for i in range(10): 
    ...:  res += np.einsum('ij,ik',x,x) 
    ...:  
In [481]: res 
Out[481]: 
array([[ 170., 220., 270.], 
     [ 220., 290., 360.], 
     [ 270., 360., 450.]]) 

Allgemeinen wenige Iterationen über eine komplexe Aufgabe ist schneller als Schub die Speichergrenzen ohne Iterationen. Zu einem bestimmten Zeitpunkt übersteigen die Speicherverwaltungskosten die Iterationskosten.

---

Diese einfache einsum ist genauso einfach mit dot, gelöst und möglicherweise schneller:

In [484]: x.T.dot(x) 
Out[484]: 
array([[17, 22, 27], 
     [22, 29, 36], 
     [27, 36, 45]]) 

---

In [486]: x=np.ones((10000000,3)) 
In [487]: timeit np.einsum('ij,ik',x,x) 
426 ms ± 151 µs per loop (mean ± std. dev. of 7 runs, 1 loop each) 

In [488]: x1=np.ones((50000000,3)) 
In [490]: timeit np.einsum('ij,ik',x1,x1) 
2.14 s ± 15.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

In [493]: %%timeit 
    ...: res = np.zeros((3,3)) 
    ...: x2 = x1.reshape(5,-1,3) 
    ...: for i in range(5): 
    ...: x3 = x2[i] 
    ...: res += np.einsum('ij,ik',x3,x3) 
2.1 s ± 5.74 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

Also auch wenn ich kein Speicherlimit noch schlagen bin, Chunking gibt mir eine leichte Geschwindigkeitsverbesserung. (obwohl ich nicht weit von den Speichergrenzen entfernt bin; einige übrig gebliebene Items im ipython-History-Stack können mich überreden).

Ein nur zum Vergleich des @ (die gleichen wie dot für 2d)

In [494]: %%timeit 
    ...: res = np.zeros((3,3)) 
    ...: x2 = x1.reshape(5,-1,3) 
    ...: for i in range(5): 
    ...: x3 = x2[i] 
    ...: res += x3.T@x3 
537 ms ± 9.62 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 

In [495]: timeit x1.T@x1 
530 ms ± 1.35 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 
In [496]: timeit x.T@x 
106 ms ± 1.41 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

Bei dieser Größe Chunking hilft nicht, wenn dot verwendet.