эффективный алгоритм вместо цикла

Question

У меня есть набор данных, где каждый из образцов имеет структуру, подобную этой

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

, например:

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

поэтому для каждый образец мне нужно вычислить точечного произведения между каждым элементом x с соответствующим элементом y того же индекса и суммой результата. то есть:

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] 

Это весь мой код:

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  

как вы можете видеть сложность этого алгоритма является слишком высокой, а также мои образцы гораздо больше, чем это. поэтому для даже небольшого набора данных, то есть содержит 400 выборок, я должен ждать 4 часа, чтобы получить результат. Я ищу лучший способ реализовать этот алгоритм. P.S: Я думал о многопоточности или многопроцессорности, но я не уверен, что это помогает ?!

Я ценю любое предложение!

Answer 1

Вместо суммирования точечного произведения каждой пары, для чего требуются операции n * m, вы можете суммировать все векторы в каждом списке и просто делать конечный продукт, который будет выполнять только n + m.

До:

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

После:

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: еще быстрее версии, воспользовавшись NumPy:

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

Выход тот же:

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

печатает:

[[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 это показывает, что существует значительное улучшение. 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) 

Примеры выходов:

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 

Работа для двух списков 20000 элементов, каждый только взял ~ 2 секунды, в то время как я предсказываю, это заняло бы несколько часов со старым методом.

---

Причина этого в том, что вы можете группировать операции вместе. Если у вас есть следующие списки:

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

суммируя скалярное произведение каждой пары будет выглядеть следующим образом:

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 

Вы можете фактор вне u, v, w, x, y, и z элементы:

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

Затем вы можете дополнительно вынесем эти сек ums:

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

Это всего лишь точечный продукт суммированных векторов из каждого исходного списка.

Answer 2

Здесь вы ничего не можете сделать. Вы хотите получить результаты всех умножений, вам просто нужно их сделать, и это ваш алгоритм. Единственное, что вы можете сделать, это сохранить ваши результаты в хеш-таблице, если вы знаете, что у вас много повторяющихся результатов, но если вы этого не сделаете, это будет очень дорого. Кстати, многопоточность может заставить вашу программу работать быстрее, но она никогда не улучшит ее сложность, а именно количество необходимых операций.

Answer 3

Вы также можете обойти необходимость itertools.product непосредственно делает скалярное произведение на внутренних матриц:

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:

На коротких списков (менее нескольких тысяч элементов), это будет Быстрее, чем ответ Клаудиу (удивительный). Его будет лучше масштабируется над этими числами:

Использование контрольной Клаудии в:

# 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