efficiente algoritmo invece di loop

Question

Ho un insieme di dati in cui ciascun campione ha una struttura simile a questo

X=[ [[],[],[],[]], [[],[]] , [[],[],[]] ,[[][]]] 

ad esempio:

X=np.array([ [ [1,2,3], [2,4,5] ,[2,3,4] ] , [ [5,6], [6,6] ] , [[2,3,1],[2,3,10],[23,1,2],[1,4,5]] ] ,"object") 

Y=np.array([ [ [12,14,15] ,[12,13,14] ] , [ [15,16], [16,16] ] , [[22,23,21],[32,33,11],[12,44,55]] ] ,"object") 

Come ogni campione devo calcolare la punto prodotto tra ogni elemento di x con l'elemento corrispondente di y dello stesso indice e somma il risultato. cioè:

result=0 

for i in range(3): 
    for n,m in itertools.product(X[i],Y[i]): 
     print "%s, %s" % (n,m) 
     result+=np.dot(n,m) 

    .....:   
[1, 2, 3], [12, 14, 15] 
[1, 2, 3], [12, 13, 14] 
[2, 4, 5], [12, 14, 15] 
[2, 4, 5], [12, 13, 14] 
[2, 3, 4], [12, 14, 15] 
[2, 3, 4], [12, 13, 14] 
[5, 6], [15, 16] 
[5, 6], [16, 16] 
[6, 6], [15, 16] 
[6, 6], [16, 16] 
[2, 3, 1], [22, 23, 21] 
[2, 3, 1], [32, 33, 11] 
[2, 3, 1], [12, 44, 55] 
[2, 3, 10], [22, 23, 21] 
[2, 3, 10], [32, 33, 11] 
[2, 3, 10], [12, 44, 55] 
[23, 1, 2], [22, 23, 21] 
[23, 1, 2], [32, 33, 11] 
[23, 1, 2], [12, 44, 55] 
[1, 4, 5], [22, 23, 21] 
[1, 4, 5], [32, 33, 11] 
[1, 4, 5], [12, 44, 55] 

Questo è tutto il mio codice:

print "***build kernel***" 
     K = np.zeros((n_samples, n_samples)) 
     for i in range(n_samples): 
      for j in range(n_samples): 

       K[i,j] = self.kernel(X[i], X[j]) 

def kernel(x1,x2): 
    N=8 #number of objects 
    result=0 
    for i in xrange(N): 
     for n,m in itertools.product(x1[i],x2[i]): 
      result+=np.dot(n,m) 
    return result  

come si può vedere la complessità di questo algoritmo è troppo alto e anche i miei campioni sono molto più grande di questo. quindi, anche per un piccolo set di dati, cioè contiene 400 campioni, devo aspettare 4 ore per ottenere il risultato. Sto cercando un modo migliore per implementare questo algoritmo. P.S: stavo pensando al multithreading o al multiproccessing ma non sono sicuro che sia d'aiuto ?!

Apprezzo qualsiasi suggerimento!

Answer 1

Invece di sommare il prodotto punto di ciascuna coppia, che richiede le operazioni n * m, è possibile sommare tutti i vettori in ogni elenco e fare solo il prodotto punto finale, che richiederà solo le operazioni n + m.

Prima:

def calc_slow(L1, L2): 
    result = 0 
    for n, m in itertools.product(L1, L2): 
     result += np.dot(n, m) 
    return result 

Dopo:

def calc_fast(L1, L2): 
    L1_sums = np.zeros(len(L1[0])) 
    L2_sums = np.zeros(len(L2[0])) 
    for vec in L1: 
     L1_sums += vec 
    for vec in L2: 
     L2_sums += vec 
    return np.dot(L1_sums, L2_sums) 

EDIT: Ancora più veloce versione, approfittando della NumPy:

def calc_superfast(L1, L2): 
    return np.dot(np.array(L1).sum(0), 
        np.array(L2).sum(0)) 

L'uscita è la stessa:

print X[0], Y[0], calc_slow(X[0], Y[0]) 
print X[0], Y[0], calc_fast(X[0], Y[0]) 

stampe:

[[1, 2, 3], [2, 4, 5], [2, 3, 4]] [[12, 14, 15], [12, 13, 14]] 711 
[[1, 2, 3], [2, 4, 5], [2, 3, 4]] [[12, 14, 15], [12, 13, 14]] 711.0 

Timing dimostra che non v'è un miglioramento significativo. Codice Timing:

import random 
import time 
def rand_vector(size=3): 
    return [random.randint(1, 100) for _ in xrange(3)] 
def rand_list(length=200): 
    return [rand_vector() for _ in xrange(length)] 

print "Generating lists..." 
L1 = rand_list(200) 
L2 = rand_list(200) 

print "Running slow..." 
s = time.time() 
print calc_slow(L1, L2) 
print "Slow for (%d, %d) took %.2fs" % (len(L1), len(L2), time.time() - s) 

print "Running fast..." 
s = time.time() 
print calc_fast(L1, L2) 
print "Fast for (%d, %d) took %.2fs" % (len(L1), len(L2), time.time() - s) 

uscite del campione:

Generating lists... 
Running slow... 
75715569 
Slow for (100, 100) took 1.48s 
Running fast... 
75715569.0 
Fast for (100, 100) took 0.03s 

Generating lists... 
Running slow... 
309169971 
Slow for (200, 200) took 5.29s 
Running fast... 
309169971.0 
Fast for (200, 200) took 0.04s 

Running fast... 
3.05185703539e+12 
Fast for (20000, 20000) took 1.94s 

L'operazione per due elenchi di 20000 elementi ha preso ogni solo ~ 2 secondi, mentre prevedo ci vorrebbero diverse ore con il vecchio metodo.

---

Il motivo per cui funziona è che è possibile raggruppare le operazioni insieme. Supponendo di avere le seguenti liste:

L1 = [a, b, c], [d, e, f], [g, h, i] 
L2 = [u, v, w], [x, y, z] 

sommando poi il prodotto scalare di ogni coppia sarebbe simile a questa:

a*u + b*v + c*w + a*x + b*y + c*z + 
d*u + e*v + f*w + d*x + e*y + f*z + 
g*u + h*v + i*w + g*x + h*y + i*z 

Si può scomporre la u, v, w, x, y, e z elementi:

u*(a + d + g) + v*(b + e + h) + w*(c + f + i) + 
x*(a + d + g) + y*(b + e + h) + z*(c + f + i) 

Quindi è possibile ulteriore fattore fuori quelli somme:

(u + x)*(a + d + g) + (v + y)*(b + e + h) + (w + z)*(c + f + i) 

Quale è solo il prodotto punto dei vettori sommati da ciascuna lista iniziale.

Answer 2

Non c'è niente che tu possa fare qui. Vuoi ottenere i risultati di tutte le moltiplicazioni, devi solo farle, ed è quello che fa il tuo algoritmo. Una delle poche cose che puoi fare è archiviare i tuoi risultati in una tabella hash, nel caso in cui tu sappia che hai molti risultati duplicati, ma se non lo farai ti costerà molta memoria. A proposito, il multithreading potrebbe far funzionare il tuo programma più velocemente, ma non migliorerà mai la sua complessità, che è il numero di operazioni necessarie.

Answer 3

È inoltre possibile bypassare la necessità di itertools.product effettuando direttamente il prodotto scalare su matrici interne:

def calc_matrix(l1, l2): 
    return np.array(l1).dot(np.array(l2).T).sum() 

def kernel(x1, x2): 
    return sum(
     calc_matrix(l1, l2) 
     for l1, l2 in zip(x1, x2) 
    ) 

Edit:

nelle liste brevi (meno di qualche migliaio di elementi) questa volontà essere più veloce della risposta (fantastica) di Claudiu. La sua scalerà meglio sopra questi numeri:

Uso benchmark di Claudiu:

# len(l1) == 500 

In [9]: %timeit calc_matrix(l1, l2) 
10 loops, best of 3: 8.11 ms per loop 

In [10]: %timeit calc_fast(l1, l2) 
10 loops, best of 3: 14.2 ms per loop 

# len(l2) == 5000 

In [19]: %timeit calc_matrix(l1, l2) 
10 loops, best of 3: 61.2 ms per loop 

In [20]: %timeit calc_fast(l1, l2) 
10 loops, best of 3: 56.7 ms per loop