ускорение продуктов numpy kronecker - PullRequest
7 голосов
/ 25 августа 2011

Я работаю над своим первым большим проектом на Python.У меня есть одна функция, в которой есть следующий код:

            # EXPAND THE EXPECTED VALUE TO APPLY TO ALL STATES,
            # THEN UPDATE fullFnMat
            EV_subset_expand = np.kron(EV_subset, np.ones((nrows, 1)))
            fullFnMat[key] = staticMat[key] + EV_subset_expand                

В моем профилировщике кода кажется, что этот продукт kronecker на самом деле занимает огромное количество времени.

Function                                                                                        was called by...
                                                                                                    ncalls  tottime  cumtime
/home/stevejb/myhg/dpsolve/ootest/tests/ddw2011/profile_dir/BellmanEquation.py:17(bellmanFn)    <-      19   37.681   38.768  /home/stevejb/myhg/dpsolve/ootest/tests/ddw2011/profile_dir/dpclient.py:467(solveTheModel)
{numpy.core.multiarray.concatenate}                                                             <-     342   27.319   27.319  /usr/lib/pymodules/python2.7/numpy/lib/shape_base.py:665(kron)
/home/stevejb/myhg/dpsolve/ootest/tests/ddw2011/profile_dir/dpclient.py:467(solveTheModel)      <-       1   11.041   91.781  <string>:1(<module>)
{method 'argsort' of 'numpy.ndarray' objects}                                                   <-      19    7.692    7.692  /usr/lib/pymodules/python2.7/numpy/core/fromnumeric.py:597(argsort)
/usr/lib/pymodules/python2.7/numpy/core/numeric.py:789(outer)                                   <-     171    2.526    2.527  /usr/lib/pymodules/python2.7/numpy/lib/shape_base.py:665(kron)
{method 'max' of 'numpy.ndarray' objects}                                                       <-     209    2.034    2.034  /home/stevejb/myhg/dpsolve/ootest/tests/ddw2011/profile_dir/dpclient.py:391(getValPolMatrices)

Есть ли способ получить более быстрые продукты Kronecker в Numpy?Похоже, это не должно занять столько времени, сколько есть.

Ответы [ 3 ]

7 голосов
/ 25 августа 2011

Вы, конечно, можете взглянуть на источник для np.kron. Его можно найти в numpy/lib/shape_base.py, и вы можете увидеть, есть ли улучшения, которые можно сделать, или упрощения, которые могут сделать его более эффективным. В качестве альтернативы вы можете написать свой собственный, используя Cython или какой-либо другой язык привязки к языку низкого уровня, чтобы попытаться добиться лучшей производительности.

Или, как сказал @matt, что-то вроде следующего может быть быстрее:

import numpy as np
nrows = 10
a = np.arange(100).reshape(10,10)
b = np.tile(a,nrows).reshape(nrows*a.shape[0],-1) # equiv to np.kron(a,np.ones((nrows,1)))

или

b = np.repeat(a,nrows*np.ones(a.shape[0],np.int),axis=0)

Тайминги:

In [80]: %timeit np.tile(a,nrows).reshape(nrows*a.shape[0],-1)
10000 loops, best of 3: 25.5 us per loop

In [81]: %timeit np.kron(a,np.ones((nrows,1)))
10000 loops, best of 3: 117 us per loop

In [91]: %timeit np.repeat(a,nrows*np.ones(a.shape[0],np.int),0)
100000 loops, best of 3: 12.8 us per loop

Использование np.repeat для массивов размеров в приведенном выше примере дает довольно хорошее ускорение в 10 раз, что не так уж и плохо.

2 голосов
/ 25 августа 2011

Может быть np.kron() выделяет память, а затем вы ее выбрасываете. Попробуйте использовать np.tile() вместо этого. Я не знаю, выделяет ли это больше памяти или играет ли уловки индексирования под прикрытием. Если вы только умножаете EV_subset на единицу, вам не нужно звонить np.kron().

1 голос
/ 31 июля 2014

Может помочь следующее (в общем случае, когда один из массивов не является «единицей»). Пример для двух массивов A, B формы (a, b, c) и (d, e, f); Обобщите по мере необходимости.

Получает это за одну операцию умножения и быстрого изменения формы.

kprod = A[:,newaxis,:,newaxis,:,newaxis] * B[newaxis,:, newaxis,:, newaxis,:]
#
# kprod.shape = (a,d,b,e,c,f) now; is full outer product with desired arrangement
# in memory.
kprod.shape = (a*d,b*e,c*f)  # reshape 'in place' 

(возможно, это крона (B, A) вместо крона (A, B); при необходимости поменяйте местами A & B)

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...