Эффективное вычисление функции по элементам в Python

Question

У меня есть следующая проблема оптимизации. Учитывая два np.arrays X, Y и функцию K Я хотел бы как можно быстрее вычислить матричную погрешность gram_matrix, где элемент (i,j)-th вычисляется как K(X[i],Y[j]).

Здесь есть реализация с использованием вложенных for-loops, которые признаны самыми медленными для решения таких проблем.

def proxy_kernel(X,Y,K): 
    gram_matrix = np.zeros((X.shape[0], Y.shape[0])) 
    for i, x in enumerate(X): 
     for j, y in enumerate(Y): 
      gram_matrix[i, j] = K(x, y) 
    return gram_matrix 

Любая помощь действительно оценена.

Answer 1

np.vectorize делает некоторое улучшение скорости - около 2x (здесь я использую math.atan2 как функцию черного ящика, которая принимает 2 скалярных аргумента).

In [486]: X=np.linspace(0,1,100) 
In [487]: K_vect=np.vectorize(math.atan2) 

In [488]: timeit proxy_kernel(X,X,math.atan2) 
100 loops, best of 3: 7.84 ms per loop 

In [489]: timeit K_vect(X[:,None],X) 
100 loops, best of 3: 3.49 ms per loop 

In [502]: timeit np.arctan2(X[:,None],X) # numpy compiled loop 
1000 loops, best of 3: 871 µs per loop 

где

def proxy_kernel(X,Y,K): 
    gram_matrix = np.zeros((X.shape[0], Y.shape[0])) 
    for i, x in enumerate(X): 
      for j, y in enumerate(Y): 
        gram_matrix[i, j] = K(x, y) 
    return gram_matrix 

Пока K черный ящик, вы ограничены по времени, которое требуется, чтобы вызвать K в X.shape[0]*Y.shape[0] раз. Вы можете попытаться свести к минимуму время итерации, но вы все равно ограничены всеми этими вызовами функций.

---

https://stackoverflow.com/a/29733040/901925 ускоряет расчет с Gausian ядра, воспользовавшись параметром функции np.linalg.normaxis.

Answer 2

Вы можете, конечно, по крайней мере, векторизации внутренний цикл:

def proxy_kernel_vect(X, Y, K): 
    K_vect = np.vectorize(K) 
    gram_matrix = np.zeros((X.shape[0], Y.shape[0])) 
    for i, x in enumerate(X): 
     gram_matrix[i] = K_vect(x, Y) 
    return gram_matrix 

Это дает хорошее улучшение с относительно длинными массивами:

In [15]: a = np.array(range(1000)) 
    ...: b = np.array(range(1000)) 
    ...: 

In [16]: %timeit proxy_kernel(a, b, k) 
1 loops, best of 3: 665 ms per loop 

In [17]: %timeit proxy_kernel_vect(a, b, k) 
1 loops, best of 3: 266 ms per loop 

где k просто lambda x, y: x+y.

Answer 3

Вы также можете попробовать vectorize декоратор от numba модуль.

вас конкретная проблема легко решается с помощью vectorize и Numpy broadcasting:

from numba import vectorize 

@vectorize(['float64(float64, float64)']) 
def K(x,y): 
    return x + y 

a = np.arange(1000) 
b = np.arange(1000) 

gram_array = K(a[None,:], b[:, None])