Attualmente sto provando a calcolare la somma di tutta la somma di sottoquadri in una matrice di valori 10.000 x 10.000. Per fare un esempio, se il mio array è stato:Come posso vettorizzare e accelerare questo calcolo di grande array?
1 1 1
2 2 2
3 3 3
Voglio che il risultato sia:
1+1+1+2+2+2+3+3+3 [sum of squares of size 1]
+(1+1+2+2)+(1+1+2+2)+(2+2+3+3)+(2+2+3+3) [sum of squares of size 2]
+(1+1+1+2+2+2+3+3+3) [sum of squares of size 3]
________________________________________
68
Così, come un primo tentativo ho scritto un codice python molto semplice per farlo. Come era in O (k^2.n^2) (n essendo la dimensione del grande array e k la dimensione dei sottosquadri che stiamo ottenendo), l'elaborazione è stata terribilmente lunga. Ho scritto un altro algoritmo in O (n^2) per accelerarlo:
def getSum(tab,size):
n = len(tab)
tmp = numpy.zeros((n,n))
for i in xrange(0,n):
sum = 0
for j in xrange(0,size):
sum += tab[j][i]
tmp[0][i] = sum
for j in xrange(1,n-size+1):
sum += (tab[j+size-1][i] - tab[j-1][i])
tmp[j][i] = sum
finalsum = 0
for i in xrange(0,n-size+1):
sum = 0
for j in xrange(0,size):
sum += tmp[i][j]
finalsum += sum
for j in xrange(1,n-size+1):
finalsum += (tmp[i][j+size-1] - tmp[i][j-1])
return finalsum
Quindi questo codice funziona correttamente. Data una matrice e una dimensione di sottoquadri, restituirà la somma dei valori in tutti questi sottoquadri. In pratica, eseguo un iterazione sulla dimensione dei sottosquadri per ottenere tutti i valori possibili.
Il problema è che questo è di nuovo troppo lungo per i grandi array (oltre 20 giorni per un array 10.000 x 10.000). L'ho cercato su google e ho imparato che avrei potuto vettorializzare le iterazioni su array con Numpy. Tuttavia, non riuscivo a capire come farlo nel mio caso ...
Se qualcuno può aiutarmi a velocizzare il mio algoritmo, o darmi una buona documentazione sull'argomento, sarò felice!
Grazie!
Penso che otterrebbe un approccio migliore per calcolare i tempi di conteggio di ciascun numero in matrice ... – Sayakiss
Dai un'occhiata alla mia modifica: Prendo un algoritmo O (n^2) ... – Sayakiss