Является ли матричное умножение медленнее, чем цикл по точечному произведению в numpy?

Я пишу код numpy для вычисления автокорреляции. Я пытаюсь улучшить производительность своей реализации.

Я пробовал два подхода: матричное умножение на представлениях массива и скалярное произведение на срезах массива в цикле for. К моему удивлению, первый подход кажется намного медленнее.

Функция принимает вектор x и максимальное смещение k и возвращает скалярное произведение вектора со смещенным вектором для каждого сдвига i.

def acorr_aview(x, k):
    return np.dot([x[i:-k+i] for i in range(k)], x[:-k])

def acorr_loop(x, k):
    return np.array([np.dot(x[i:-k+i],x[:-k]) for i in range(k)])

Я ожидал, что acorr_aview будет иметь лучшую производительность из-за использования матричного умножения, но, похоже, дело обстоит наоборот.

x = np.random.randn(10000)
k = 100

%timeit acorr_aview(x,k)
%timeit acorr_loop(x,k)

3.32 ms ± 243 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
753 µs ± 33.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Почему acorr_loop намного быстрее? Спасибо.

Изменить: Для сравнения:

A = np.random.randn(9900,100)
v = np.random.randn(100)

%timeit np.dot(A,v)
%timeit np.array([np.dot(a,v) for a in A])

1.08 ms ± 10.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
12.4 ms ± 243 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

numpy arrays performance matrix-multiplication dot-product
person RinaldoB    schedule 03.05.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

В первом случае у вас есть (100, 9900) с точкой (9900,). Во втором вы ставите точки (9900,) над (9900,) 100 раз.

Существует компромисс между затратами на управление памятью в первом случае и затратами на итерацию во втором. Другие вопросы SO показали, что небольшое количество итераций для большой проблемы может быть быстрее, чем одно вычисление для гораздо большей проблемы.

Почему B = numpy.dot(A,x) настолько медленнее выполняет цикл B[i,:,:] = numpy.dot(A[i,:,:],x))?

В вашем случае происходит еще одна вещь - время, необходимое для создания этого большего массива:

In [366]: timeit np.array([x[i:-k+i] for i in range(k)])                             
2.62 ms ± 22.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [367]: timeit np.dot(np.array([x[i:-k+i] for i in range(k)]),x[:-k])              
3.6 ms ± 147 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [368]: %%timeit xx = np.array([x[i:-k+i] for i in range(k)]) 
     ...: np.dot(xx, x[:-k])                                                                  
1.05 ms ± 9.27 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Большой dot по-прежнему требует больше времени, чем 100 меньших, но построить этот xx — большая работа.

person hpaulj    schedule 03.05.2019
comment
Это не так просто. Смотрите мою правку для сравнения. На самом деле, acorr_loop даже быстрее, чем простое умножение матриц, поэтому за кулисами должна происходить некоторая оптимизация. Кроме того, в acorr_aview фактически не создается массив (не копируется память), это просто список представлений массива (срезов). - person RinaldoB; 03.05.2019
comment
Этот список фрагментов должен быть преобразован в массив, прежде чем точка сможет его использовать (передать его в BLAS). - person hpaulj; 03.05.2019
comment
Ваш сравнительный случай - это больше петель на меньшей точке. - person hpaulj; 03.05.2019
comment
Спасибо. В вашем примере есть какое-либо объяснение, почему преобразование срезов в массив и умножение на самом деле быстрее, чем выполнение любого из этих двух действий по отдельности? - person RinaldoB; 05.05.2019