Является ли умножение матриц медленнее, чем циклическое произведение точек на ноль? - PullRequest
Новая
       41

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

1 голос
/ 03 мая 2019

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

Я попробовал два подхода: умножение матриц на представлениях массива и скалярное произведение на срезах массива в цикле 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)

1 Ответ

1 голос
/ 03 мая 2019

В первом случае у вас есть (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 - большая работа.

...