28. 计算移动平均值函数

一. 定义

1.移动平均值是什么?

(1)移动平均值,是一种统计指标,用于观测一组随时间变化的量。

(2)M-移动平均值,是最后 M 个数的移动平均值。一定要注意,这边算出的平均值是一组数,而不是一个数。

2. 移动平均值怎么算?

首先我们给出一组数据,data = ( 1, 2, 3, 4, 5, 6 ),现在我们需要计算 M = 3 时的移动平均值。那么第一个移动平均值就是(1, 2, 3)的算术平均值,第二个移动平均值就是(2, 3, 4)的算术平均值,其余同理。

3. 移动平均值的作用是什么?

给定一组数据,这组数据应该是随时间变化记录得到的,它可以是某商品一年的销量,也可以是你一年考试的成绩。通过计算这组数据的移动平均值,我们可以简单预测未来的表现。

二. 代码实现

1.函数代码

 1 vector<double> moving_average(const vector<int>& data, int m) {
 2     vector<double> m_averages;
 3 
 4     for (int i = m - 1; i < data.size(); ++i) {
 5         double current_sum = 0.0;
 6 
 7         for (int j = i - m + 1; j <= i; ++j) {
 8             current_sum += data[j];
 9         }
10         double avg = current_sum / m;
11         m_averages.push_back(avg);
12     }
13 
14     return m_averages;
15 }

2.算法分析

我们来分析一下这段代码。首先,函数传入一个需要处理的数据列,并且需要一个 M ,来告诉我们将会处理几个数的平均值。前面提到,移动平均值实际上是一组数,所以函数也应该返回一组数:这里返回一个 vector。

外层循环控制整体范围,我们希望它的下标不要超过数据的数量。每次计算 M 个数的平均值,所以应该从 M - 1 开始(如果从 M 位置开始,那么最后一个数字将不能被计算到,也就是说,返回的平均值里面,会丢掉最后一次的计算)。

内层循环控制小的范围,每次只累加固定 M 个数的部分和。在每次计算完成后,我们将当前的平均值加入到平均值组中。

不难看出,下标的开始与结束,非常复杂,不容易理解,并且算法的时间复杂度是 O(n^2),这个复杂度对于小型数据组可以接受,但是处理大型数据组的时候,难免显得力不从心。

当一件事情的解决方式并不优雅的时候,一般来说都会出错,那么我们来优化算法。

3. 优化

通过上述分析,我们得知,很多功夫都花费在计算部分和上,而这个部分和很大一部分是不变的,每次变化的,只是第一个数据和最后一个数据。立即推,我们对于重复部分不进行重复计算。优化后的代码如下:

 1 vector<double> moving_average(const vector<int>& data, int m) {
 2     vector<double> m_averages;
 3     double current_sum = 0.0;
 4 
 5     for (int i = 0; i < m - 1; ++i) {
 6         current_sum += data[i];
 7     }
 8 
 9     for (int i = m - 1; i < data.size(); ++i) {
10         current_sum += data[i];
11         double avg = current_sum / m;
12         m_averages.push_back(avg);
13         current_sum -= data[i - m + 1];
14     }
15     
16     return m_averages;
17 }

现在再来分析一下优化后的新函数。

第一个循环计算 M - 1 个部分和,这个部分和其实是缺失的,因为少了最后一个数据,但是它开启了后续的步骤。在第二个循环中,我们先把缺失的数据加进去,然后计算平均值,接着将平均值放到平均值组里,再将最前面的一个元素,从部分和中减去,这样就为下一次循环做好了准备。新函数的时间复杂度是 O(n),应对大型数据的时候,效果也很不错。

 

28. 计算移动平均值函数

上一篇:yum安装软件,出现Delta RPMs disabled because /usr/bin/applydeltarpm not installed报错


下一篇:app的meta标签