Почему B = numpy.dot (A, x) настолько медленнее, что цикл B = numpy.dot (A , x))?

Я получаю результаты эффективности, которые я не могу объяснить.

Я хочу собрать матрицу B, чьи i-ые записи B [i,:,:] = A [i,:,:]. Dot (x), где каждая A [i,:,:] является двумерной матрицей, и х.

Я могу сделать это тремя способами, чтобы проверить производительность. Я делаю произвольные ( numpy.random.randn ) матрицы A = (10,1000,1000), x = (1000,1200). Я получаю следующие результаты:

(1) одномерный многомерный точечный продукт

 B = A.dot(x) total time: 102.361 s

(2) петля через i и выполнение двумерных точечных продуктов

  # initialize B = np.zeros([dim1, dim2, dim3]) for i in range(A.shape[0]): B[i,:,:] = A[i,:,:].dot(x) total time: 0.826 s

(3) numpy.einsum

 B3 = np.einsum("ijk, kl -> ijl", A, x) total time: 8.289 s

Таким образом, вариант (2) является самым быстрым на сегодняшний день. Но, учитывая только (1) и (2), я не вижу большой разницы между ними. Как можно прокручивать и делать 2D-точечные продукты в 124 раза быстрее? Они оба используют numpy.dot. Какие-нибудь идеи?

Я включаю код, используемый для приведенных выше результатов, чуть ниже:

 import numpy as np import numpy.random as npr import time dim1, dim2, dim3 = 10, 1000, 1200 A = npr.randn(dim1, dim2, dim2) x = npr.randn(dim2, dim3) # consider three ways of assembling the same matrix B: B1, B2, B3 t = time.time() B1 = np.dot(A,x) td1 = time.time() - t print "a single dot product of A [shape = (%d, %d, %d)] with x [shape = (%d, %d)] completes in %.3f s" \ % (A.shape[0], A.shape[1], A.shape[2], x.shape[0], x.shape[1], td1) B2 = np.zeros([A.shape[0], x.shape[0], x.shape[1]]) t = time.time() for i in range(A.shape[0]): B2[i,:,:] = np.dot(A[i,:,:], x) td2 = time.time() - t print "taking %d dot products of 2D dot products A[i,:,:] [shape = (%d, %d)] with x [shape = (%d, %d)] completes in %.3f s" \ % (A.shape[0], A.shape[1], A.shape[2], x.shape[0], x.shape[1], td2) t = time.time() B3 = np.einsum("ijk, kl -> ijl", A, x) td3 = time.time() - t print "using np.einsum, it completes in %.3f s" % td3

2 Solutions collect form web for “Почему B = numpy.dot (A, x) настолько медленнее, что цикл B = numpy.dot (A , x))?”

С меньшими размерами 10 10,100,200 , я получаю аналогичный рейтинг

 In [355]: %%timeit .....: B=np.zeros((N,M,L)) .....: for i in range(N): B[i,:,:]=np.dot(A[i,:,:],x) .....: 10 loops, best of 3: 22.5 ms per loop In [356]: timeit np.dot(A,x) 10 loops, best of 3: 44.2 ms per loop In [357]: timeit np.einsum('ijk,km->ijm',A,x) 10 loops, best of 3: 29 ms per loop In [367]: timeit np.dot(A.reshape(-1,M),x).reshape(N,M,L) 10 loops, best of 3: 22.1 ms per loop In [375]: timeit np.tensordot(A,x,(2,0)) 10 loops, best of 3: 22.2 ms per loop

итерация выполняется быстрее, хотя и не так сильно, как в вашем случае.

Это, вероятно, верно, если этот итерирующий размер мал по сравнению с другими. В этом случае накладные расходы на итерацию (вызовы функций и т. Д.) Малы по сравнению с временем вычисления. И выполнение всех значений сразу использует больше памяти.

Я попробовал dot где я переформатировал A на 2d, считая, что dot делает такую реорганизацию внутри. Я удивлен, что он на самом деле самый быстрый. tensordot , вероятно, выполняет ту же перестановку (этот код, если Python читается).

einsum устанавливает einsum «суммы продуктов» с участием 4 переменных, i,j,k,m – это dim1*dim2*dim2*dim3 шагов с уровнем nditer уровня. Таким образом, чем больше индексов, тем больше пространство итераций.

Я не слишком хорошо знаком с C-API numpy, а numpy.dot – одна из таких встроенных функций, которая раньше использовалась в _dotblas .

Тем не менее, вот мои мысли.

1) numpy.dot принимает разные пути для двумерных массивов и n-мерных массивов. Из онлайн-документации numpy.dot :

Для двумерных массивов это эквивалентно матричному умножению, а для 1-D массивов – скалярному произведению векторов (без комплексного сопряжения). Для N измерений это суммарное произведение по последней оси а, а второе-последнее из b

точка (a, b) [i, j, k, m] = sum (a [i, j ,:] * b [k,:, m])

Таким образом, для 2-D массивов вам всегда гарантирован один вызов для BLAS- dgemm , однако для ND-массивов numpy может выбрать оси умножения для массивов, которые могут не соответствовать самой быстро меняющейся оси (как вы можете видеть из выдержки, которую я опубликовал ), и в результате можно было упустить всю мощь dgemm .

2) Ваш массив слишком велик для загрузки в кэш CPU. В вашем примере вы используете A с размерами (10,1000,1000) который дает

 In [1]: A.nbytes 80000000 In [2]: 80000000/1024 78125

Это почти 80MB , намного больше, чем размер вашего кеша. Таким образом, вы снова теряете большую часть dgemm .

3) Вы также часто выполняете функции несколько неточно. Известно, что функция time в Python не является точной. timeit этого используйте timeit .

Итак, имея все вышеперечисленные моменты, давайте попробуем экспериментировать с массивами, которые могут быть загружены в кеш

 dim1, dim2, dim3 = 20, 20, 20 A = np.random.rand(dim1, dim2, dim2) x = np.random.rand(dim2, dim3) def for_dot1(A,x): for i in range(A.shape[0]): np.dot(A[i,:,:], x) def for_dot2(A,x): for i in range(A.shape[0]): np.dot(A[:,i,:], x) def for_dot3(A,x): for i in range(A.shape[0]): np.dot(A[:,:,i], x)

и вот тайминги, которые я получаю (используя numpy 1.9.2 построенный против OpenBLAS 0.2.14 ):

 In [3]: %timeit np.dot(A,x) 10000 loops, best of 3: 174 µs per loop In [4]: %timeit np.einsum("ijk, kl -> ijl", A, x) 10000 loops, best of 3: 108 µs per loop In [5]: %timeit np.einsum("ijk, lk -> ijl", A, x) 10000 loops, best of 3: 97.1 µs per loop In [6]: %timeit np.einsum("ikj, kl -> ijl", A, x) 1000 loops, best of 3: 238 µs per loop In [7]: %timeit np.einsum("kij, kl -> ijl", A, x) 10000 loops, best of 3: 113 µs per loop In [8]: %timeit for_dot1(A,x) 10000 loops, best of 3: 101 µs per loop In [9]: %timeit for_dot2(A,x) 10000 loops, best of 3: 131 µs per loop In [10]: %timeit for_dot3(A,x) 10000 loops, best of 3: 133 µs per loop

Обратите внимание, что по-прежнему существует разница во времени, но не по порядку. Также обратите внимание на важность choosing the axis of multiplication . Теперь, возможно, многопользовательский разработчик может пролить свет на то, что numpy.dot действительно делает под капотом для массивов ND.