我编写了一个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毫秒。为什么我的算法这么慢?
您的算法的阶数为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)