Более быстрая свертка функций плотности вероятности в Python

Вы можете эффективно вычислить свертку всех ваших PDF-файлов, используя быстрые преобразования Фурье (БПФ): ключевым фактом является то, что БПФ свертки является произведением БПФ отдельных функций плотности вероятности. Поэтому преобразуйте каждый PDF-файл, умножьте преобразованные PDF-файлы вместе, а затем выполните обратное преобразование. Вам нужно будет дополнить каждый входной PDF-файл нулями до соответствующей длины, чтобы избежать эффектов зацикливания.

Это должно быть достаточно эффективным: если у вас есть m PDF-файлов, каждый из которых содержит n записей, то время вычисления свертки с использованием этого метода должно возрасти как (m^2)n log(mn). Во времени преобладают БПФ, и мы эффективно вычисляем m + 1 независимых БПФ (m прямых преобразований и одно обратное преобразование), каждое из массива длиной не более mn. Но, как всегда, если вам нужны реальные тайминги, вам следует профилировать.

Вот код:

import numpy.fft

def convolve_many(arrays):
    """
    Convolve a list of 1d float arrays together, using FFTs.
    The arrays need not have the same length, but each array should
    have length at least 1.

    """
    result_length = 1 + sum((len(array) - 1) for array in arrays)

    # Copy each array into a 2d array of the appropriate shape.
    rows = numpy.zeros((len(arrays), result_length))
    for i, array in enumerate(arrays):
        rows[i, :len(array)] = array

    # Transform, take the product, and do the inverse transform
    # to get the convolution.
    fft_of_rows = numpy.fft.fft(rows)
    fft_of_convolution = fft_of_rows.prod(axis=0)
    convolution = numpy.fft.ifft(fft_of_convolution)

    # Assuming real inputs, the imaginary part of the output can
    # be ignored.
    return convolution.real

Применяя это к вашему примеру, вот что я получаю:

>>> convolve_many([[0.6, 0.3, 0.1], [0.5, 0.4, 0.1], [0.3, 0.7], [1.0]])
array([ 0.09 ,  0.327,  0.342,  0.182,  0.052,  0.007])

Это основная идея. Если вы хотите изменить это, вы также можете посмотреть numpy.fft.rfft (и наоборот, numpy.fft.irfft), которые используют тот факт, что входные данные являются реальными, для создания более компактных преобразованных массивов. Вы также можете увеличить скорость, дополнив массив rows нулями, чтобы общее количество столбцов было оптимальным для выполнения БПФ. Определение «оптимального» здесь будет зависеть от реализации БПФ, но, например, степень двойки будет хорошей целью. Наконец, есть некоторые очевидные упрощения, которые можно сделать при создании rows, если все входные массивы имеют одинаковую длину. Но я оставлю эти потенциальные улучшения вам.