Почему блочная свертка намного быстрее, чем свертка? ⇐ Python

[Anonymous]

Я пытался найти способ ускорить свертку там, где существует большой диапазон значений. Методы, основанные на FFT, дают неправильный ответ в этих случаях из -за числовых ошибок. Итак, я попробовал это: < /p>

Код: Выделить всё

from scipy.signal import convolve
def block_convolve(a, b, block_size):
n = len(a) + len(b) - 1
result = np.zeros(n)

for i in range(0, len(a), block_size):
a_block = a[i:i + block_size]
for j in range(0, len(b), block_size):
b_block = b[j:j + block_size]
conv = convolve(a_block, b_block, mode='full')
result[i + j : i + j + len(conv)] += conv

return result

import numpy as np
a = np.array([0]*10000 + [10**(9*i) for i in range(10)], dtype=np.float64)
block_size = 2**13
(block_convolve(a, a, block_size) == convolve(a, a, method="direct")).all()
< /code>
Это возвращение true. block_convolve предназначен для того, чтобы быть точно эквивалентным для конверсирования. < /p>
В моей системе я вижу < /p>
%timeit block_convolve(a, a, block_size)
1.82 ms ± 192 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
%timeit convolve(a, a, method="direct")
24.8 ms ± 1.77 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

Почему это намного быстрее?

Подробнее здесь: https://stackoverflow.com/questions/794 ... onvolution