为什么我的移动平均算法这么慢？

Question

我编写了一个Fortran函数，该函数以一种非常简单的方式来计算一维数字数组的移动平均值：

function moving_average(data, w)

    implicit none

    integer, intent(in) :: w
    real(8), intent(in) :: data(:)

    integer :: n, i
    real(8) :: moving_average(size(data)-w+1)

    n = w-1

    do i=1, size(data)-n
        moving_average(i) = mean(data(i:i+n))
    end do

end function

该函数mean定义为：

real(8) function mean(data)

    implicit none

    real(8), dimension(:), intent(in) :: data

    mean = sum(data)/size(data)

end function

在moving_average具有100000个数字的数据集和1000的窗口宽度的笔记本电脑上运行该功能时，需要0.1秒。但是，该函数running_mean在这个岗位使用numpy只需要1毫秒。为什么我的算法这么慢？

Answer 1

您的算法的阶数为O（n * m），n为移动平均值的大小，m为数组的大小。

每次计算数组中的点时moving_average，都执行以下步骤：

• 提取数组的一部分
• 计算该切片的总和
• 除以常数 n

但是，moving_average(i)和moving_average(i+1)通过以下方式相关：

moving_average(i+i) = moving_average(i) + (data(i+n) - data(i-1))/n

使用此功能时，您可以将计算时间从O（n * m）减少到O（m）