Python NumPy - Есть ли более быстрый способ свернуть?

Question

У меня очень большой числовой массив (1 миллион целых чисел).Я использую np.convolve, чтобы найти «самую плотную» область этого массива.Под областью «desnsest» я подразумеваю окно фиксированной длины, которое имеет наибольшее число при суммировании окна.Позвольте мне показать вам код:

import numpy as np

example = np.array([0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,0,0,0,1,0,0,1,1,0,1,0,0,0,0,0,1,0])
window_size = 10
density = np.convolve(example, np.ones([window_size]), mode='valid')
print(density) 
# [7.0, 7.0, 8.0, 9.0, 9.0, 9.0, 8.0, 7.0, 6.0, 6.0, 5.0, 5.0, 5.0, 5.0, 4.0, 4.0, 4.0, 4.0, 4.0, 3.0, 3.0, 4.0, 3.0]

Затем я могу использовать np.argmax(density), чтобы получить начальный индекс области с наивысшей плотностью 3.

В любом случае, в этом примере он работаетбыстро.но при свертывании более миллиона элементов массива с размером окна 10 000 требуется 2 секунды.если я выберу размер windows_size 500 000, потребуется 3 минуты.

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

Спасибо за вашу помощь!

Answer 1

Это - это то, как вы можете использовать встроенные функции реального БПФ NumPy для свертки в 1 измерении:

import numpy, numpy.fft.fftpack_lite

def fftpack_lite_rfftb(buf, s):
    n = len(buf)
    m = (n - 1) * 2
    temp = numpy.empty(m, buf.dtype)
    numpy.divide(buf, m, temp[:n])
    temp[n:m] = 0
    return numpy.fft.fftpack_lite.rfftb(temp[:m], s)

def fftconvolve(x, y):
    xn = x.shape[-1]
    yn = y.shape[-1]
    cn = xn + yn - (xn + yn > 0)
    m = 1 << cn.bit_length()
    s = numpy.fft.fftpack_lite.rffti(m)  # Initialization; can be factored out for performance
    xpad = numpy.pad(x, [(0, 0)] * (len(x.shape) - 1) + [(0, m - xn)], 'constant')
    a = numpy.fft.fftpack_lite.rfftf(xpad, s)  # Forward transform
    ypad = numpy.pad(y, [(0, 0)] * (len(y.shape) - 1) + [(0, m - yn)], 'constant')
    b = numpy.fft.fftpack_lite.rfftf(ypad, s)  # Forward transform
    numpy.multiply(a, b, b)  # Spectral multiplication
    c = fftpack_lite_rfftb(b, s)  # Backward transform
    return c[:cn]

# Verify convolution is correct
assert (lambda a, b: numpy.allclose(fftconvolve(a, b), numpy.convolve(a, b)))(numpy.random.randn(numpy.random.randint(1, 32)), numpy.random.randn(numpy.random.randint(1, 32)))

Имейте в виду, что это заполнение неэффективно для свертки векторовсо значительно отличающимися размерами (> 100%);вам понадобится метод линейного комбинирования, такой как overlap-add, чтобы уменьшить свертку.

Answer 2

cumsum = np.cumsum(np.insert(example, 0, 0))

density2 = cumsum[window_size:]-cumsum[:-window_size]

np.all(density2 == density)

True

(удалить вставку, если вы можете жить без первого значения ...)

Answer 3

Попробуйте использовать scipy.signal.convolve.У него есть опция для вычисления свертки с использованием быстрого преобразования Фурье (БПФ), которое должно быть намного быстрее для упомянутых вами размеров массива.

Использование массива example длиной 1000000 и свертывание его смассив длины 10000, np.convolve занял на моем компьютере около 1,45 секунды, а scipy.signal.convolve - 22,7 миллисекунды.