Не можете понять, почему большая векторизация медленнее, чем меньшая векторизация в этом случае?

Question

Я сталкиваюсь с практической проблемой, когда больше векторизации медленнее, чем меньше векторизации. Я упрощаю основную проблему в следующей игрушечной модели. В следующих кодах я использую два разных метода для реализации одной и той же функциональности. f1 использует один l oop, f2 использует два цикла. Наивно будем думать, что f1 быстрее f2. Однако f2 быстрее, чем f1. Я не могу понять, почему это происходит.

import numpy as np
def time_function(f, *args):
    import time
    tic = time.time()
    f(*args)
    toc = time.time()
    return toc - tic

def f2(X, Y):
    d = np.zeros((X.shape[0], Y.shape[0]))
    for i in range(X.shape[0]):
        for j in range(Y.shape[0]):
            d[i,j] = np.sum(np.square(X[i] - Y[j])) 
    return d

def f1(X, Y):
    d = np.zeros((X.shape[0], Y.shape[0]))
    for i in range(X.shape[0]):
        d[i] = np.sum(np.square(Y - X[i]), axis=1) 
    return d

X = np.ones((500, 3072))
Y = np.ones((5000, 3072))

time2 = time_function(f2,X,Y)
print('Two loop version took %f seconds' % time2)

time1 = time_function(f1,X,Y)
print('One loop version took %f seconds' % time1)

Two loop version took 24.691270 seconds
One loop version took 31.785896 seconds

Answer 1

Я полагаю, что виновник скрывается в f1 :

d[i] = np.sum(np.square(Y - X[i]), axis=1) 

Вы вычитаете X [i] из всего массива Y каждую итерацию, что вызывает интенсивное вещание, которое включает в себя итерацию в диапазоне 0 <= i <= 5000 </strong>, а f2 вычитает два различных значения, ограниченные 0 <= i <= 500 </strong>

Answer 2

На моей машине f1 немного быстрее. Но полностью векторизованная версия

D3=(np.square(Y[None,:,:]-X[:,None,:])).sum(axis=2)

выдает ошибку памяти, поскольку она должна создать (500, 5000, 3072) массив (57G).

Существует компромисс между итерациями и памятью управление. Часто несколько итераций относительно сложной задачи выполняются быстрее, чем один шаг, требующий выделения большей матрицы. В вашем случае есть разница Y-X, но затем нужно также сделать square (такой же большой размер), прежде чем уменьшать размеры с помощью sum.

In [23]: timeit -n1 -r1 f2(X,Y)                                                                
1min 21s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)
In [24]: timeit -n1 -r1 f1(X,Y)                                                                
1min 13s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

Вариации на f1, который повторяется в 5000 строках Y (вместо 500 X) раз в 1min 25s. Несколько итераций обычно лучше, чем многие, при условии, что проблемы с управлением памятью вас не оштрафуют.

numba

Итеративная, но скомпилированная версия, использующая numba, заметно лучше:

In [32]: import numba 
    ...: @numba.jit(nopython=True) 
    ...: def f3(X, Y): 
    ...:     d = np.zeros((X.shape[0], Y.shape[0])) 
    ...:     for i in range(X.shape[0]): 
    ...:         for j in range(Y.shape[0]): 
    ...:             d[i,j] = np.sum(np.square(X[i] - Y[j]))  
    ...:     return d 
    ...:                                                                                       
In [33]: D3=f3(X,Y)                                                                            
In [34]: np.allclose(D,D3)                                                                     
Out[34]: True
In [35]: timeit -n1 -r1 f3(X,Y)                                                                
20 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

и явное повторение суммы сокращает время еще раз:

In [36]: @numba.jit(nopython=True) 
    ...: def f4(X, Y): 
    ...:     d = np.zeros((X.shape[0], Y.shape[0])) 
    ...:     for i in range(X.shape[0]): 
    ...:         for j in range(Y.shape[0]): 
    ...:             for k in range(X.shape[1]): 
    ...:                 d[i,j] += (X[i,k] - Y[j,k])**2  
    ...:     return d 
    ...:      
    ...:                                                                                       
In [37]: D4 = f4(X,Y)                                                                          
In [38]: np.allclose(D,D4)                                                                     
Out[38]: True
In [39]: timeit -n1 -r1 f4(X,Y)                                                                
10.7 s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)

Answer 3

Я вижу итерацию в обоих определениях. Векторизация дает выигрыш только на больших количествах! Вы эффективно за один раз векторизуете только одну строку значений. Цикл Python более чем способен справиться с этим, затраты на поиск и настройку векторизованных вычислений по сравнению с этим занимает слишком много времени. Ваш f1 не полностью векторизован из-за итерации. Таким образом, это сравнение не справедливо для векторизации, когда итерации будет достаточно.

tl; dr имеют достаточно значений, чтобы «настройка» векторизации компенсировалась выигрышами самой векторизации.