wydajny algorytm zamiast zapętlenie

Question

Mam zestaw danych, gdzie każdy próbki ma strukturę podobną do tej

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

na przykład:

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") 

więc dla każda próbka muszę obliczyć kropka pomiędzy każdym elementem x z odpowiednim elementem y tego samego indeksu i suma wyniku. tj:

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] 

To cały mój kod:

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  

jak widać złożoność tego algorytmu jest zbyt wysoka, a także moje próbki są znacznie większe niż to. więc nawet dla małego zestawu danych, tj. zawierającego 400 próbek, muszę poczekać 4 godziny, aby uzyskać wynik. Szukam lepszego sposobu wdrożenia tego algorytmu. P.S: Myślałem o wielowątkowości lub multiproccessingu, ale nie jestem pewien, czy to pomaga ?!

Doceniam każdą sugestię!

Answer 1

Zamiast zsumowanie iloczynu skalarnego z każdej pary, która wymaga n * m operacji można podsumować wszystkich wektorów w każdej listy i po prostu zrobić ostateczną iloczynu skalarnego, która zajmie tylko n + m operacje.

Przed:

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

Po:

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: jeszcze szybsza wersja, wykorzystując numpy:

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

Wyjście jest takie samo:

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

drukuje:

[[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 pokazuje, że istnieje znacząca poprawa. Kod czasowy:

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) 

wyjścia Próbka:

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 

Operacja na dwóch listach 20000 elementów wziął każdy tylko ~ 2 sekundy, natomiast przewiduję zajęłoby kilka godzin ze starą metodą.

---

Powodem tego działania jest możliwość pogrupowania operacji. Zakładając, że masz następujące listy:

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

Następnie zsumowanie iloczyn skalarny każdej pary będzie wyglądać następująco:

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 

Można czynnik się z u, v, w, x, y i z elementy:

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

Następnie można dodatkowo czynnik z tych sumy:

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

Co jest tylko iloczynem punktowym sumowanych wektorów z każdej początkowej listy.

Answer 2

Nic nie możesz tu zrobić. Chcesz uzyskać wyniki wszystkich multiplikacji, po prostu musisz je wykonać, i to właśnie robi twój algorytm. Jedną z rzeczy, które możesz zrobić, to przechowywać wyniki w tablicy hashtable, na wypadek, gdyby wiesz, że masz dużo powielonych wyników, ale będzie to kosztować dużo pamięci, jeśli tego nie zrobisz. Nawiasem mówiąc, wielowątkowość może sprawić, że twój program będzie działał szybciej, ale nigdy nie poprawi jego złożoności, czyli liczby wymaganych operacji.

Answer 3

Można też ominąć konieczność itertools.product bezpośrednio robi produkt kropka na wewnętrznych matryc:

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:

na krótkich listach (mniej niż kilka tysięcy elementów) to wolę być szybszym od odpowiedzi Claudiu (niesamowitej). Jego skala będzie lepiej nad tymi numerami:

Korzystanie odniesienia Claudiu za:

# 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