简单的移动平均算法
4.64/5 (39投票s)
简单的移动平均算法
引言
我需要一个运行平均值来监控 CPU 利用率，于是我编写了一个小型类来执行计算。在编写代码的过程中，我意识到即使是像运行平均算法这样简单的东西，也需要仔细考虑才能写得好。因此，我写了这篇文章给初学者，来说明即使是简单的算法也需要仔细考虑。
什么是运行平均值？
运行平均值（也称为移动平均值）可以通过不同的方式实现。有关详细描述，请参阅 wikipedia。
简单移动平均
简单移动平均是前面 n 个数据点的未加权平均值（列表中所有项的总和除以列表中的项数）。这是最容易实现的运行平均值，也是我在本文中说明的。
加权移动平均
加权移动平均是一种平均值，其中列表中的数据点被赋予不同的乘数。这使得列表中的某些项比其他项更重要（获得更高的权重）。例如，您可能希望旧值比新值更重要，或者反之亦然。
暴力实现
简单移动平均值取样本值并除以样本计数。基本的实现可能看起来像这样
using System;
using System.Collections.Generic;
using System.Text;
namespace AveragerTest
{
public class BruteForce
{
protected float[] samples;
protected int idx;
public float Average
{
get
{
float total=0;
for (int i=0; i<samples.Length; i++)
{
total+=samples[i];
}
return total/samples.Length;
}
}
public BruteForce(int numSamples)
{
if (numSamples <= 0)
{
throw new ArgumentOutOfRangeException(
"numSamples can't be negative or 0.");
}
samples = new float[numSamples];
idx = 0;
}
public void AddSample(float val)
{
samples[idx] = val;
if (++idx == samples.Length)
{
idx = 0;
}
}
}
}
事实上，这让我想起了我刚开始用 Commodore BASIC 编程时写的一个算法！这个算法有几个问题
- 在样本数组完全加载之前，
Average计算会包含未加载（且为零）的样本值。这会导致平均值不正确。 - 对于大型样本量，该算法非常低效，每次取平均值时都必须对样本进行求和。
- 该算法实现了一个循环列表。将循环列表的实现与运行平均算法的实现分离开来，难道不好吗？
- 没有好的方法可以用加权运行平均值等来替换简单运行平均值，因为该类没有实现一个促进用例灵活性的接口。
更好的实现
分离集合和迭代逻辑
我认为，第一步是分离迭代逻辑。我们必须小心，因为我们需要的循环列表不仅仅是一个迭代器——我们实际上也必须在列表中设置值。迭代器不允许这样做。来自 MSDN
只要集合保持不变，枚举器就会保持有效。如果对集合进行了更改，例如添加、修改或删除元素，枚举器将永久失效，下一次调用 MoveNext 或 Reset 将引发 InvalidOperationException。
将样本列表的管理改为 循环列表 消除了两个问题
- 列表管理与算法解耦。
- 我们可以使用循环列表的
Count方法来获取已加载项的计数，而不仅仅是列表中总项数。
此外，它还利用了代码重用并有助于调试——我们可以将循环列表的测试与运行平均类中的问题隔离开来。换句话说，很容易为循环列表编写单元测试，验证其操作，然后编写单元测试来验证平均值是否正常工作。
新代码看起来像这样
using System;
using System.Collections.Generic;
using System.Text;
using Clifton.Collections.Generic;
namespace AveragerTest
{
public class BruteForce
{
CircularList<float> samples;
public float Average
{
get
{
float total=0;
foreach(float v in samples)
{
total+=v;
}
return total/samples.Count;
}
}
public BruteForce(int numSamples)
{
if (numSamples <= 0)
{
throw new ArgumentOutOfRangeException(
"numSamples can't be negative or 0.");
}
samples = new CircularList<float>(numSamples);
}
public void AddSample(float val)
{
samples.Value = val;
samples.Next();
}
}
}
这已经是一个更干净的实现了！
性能
下一个问题是性能。对于大样本量，我们不希望遍历整个样本来获取总和。管理一个运行总数更有意义。这需要在添加样本值时进行一些逻辑处理，以确定是否已经存在样本，以便可以将其从总数中减去
public void AddSample(float val)
{
if (samples.Count == samples.Length)
{
total -= samples.Value;
}
samples.Value = val;
total += val;
samples.Next();
}
并且 Average getter 不再需要对所有样本求和
public float Average
{
get { return total/samples.Count; }
}
但性能真的更好吗？
这总是一个问题，而且取决于使用情况！可以说，如果添加的样本与取平均值的次数的比例非常高，那么第一种方法可能性能更好。例如，您可能在取平均值之间添加了数百万个样本，而样本量可能只有一百个。在这种情况下，保持总数当前的开销可能远远大于即时计算总数的开销。
因此，关于性能的正确答案是选择适合您需求的算法。我上面描述的算法是我认为的典型情况，即在每个新样本之后都会取平均值，在这种情况下，使用运行总数是有意义的，尤其是当样本量很大时。
提高可用性
通过提供程序员可以使用而不是直接使用类的接口，可以提高可用性。通过使用接口，程序员可以创建正确的移动平均算法，而代码无需知道实际构建的是哪种（简单或加权）算法。应用程序的另一部分可以做出此决定。
public interface IMovingAverage
{
float Average { get;}
void AddSample(float val);
void ClearSamples();
void InitializeSamples(float val);
}
注释、错误检查和锦上添花
最终的实现，包含一些额外的错误检查以及清除平均值或用特定值预加载样本的功能，如下所示
using System;
using Clifton.Collections.Generic;
namespace Clifton.Tools.Data
{
public class SimpleMovingAverage : IMovingAverage
{
CircularList<float> samples;
protected float total;
/// <summary>
/// Get the average for the current number of samples.
/// </summary>
public float Average
{
get
{
if (samples.Count == 0)
{
throw new ApplicationException("Number of samples is 0.");
}
return total / samples.Count;
}
}
/// <summary>
/// Constructor, initializing the sample size to the specified number.
/// </summary>
public SimpleMovingAverage(int numSamples)
{
if (numSamples <= 0)
{
throw new ArgumentOutOfRangeException(
"numSamples can't be negative or 0.");
}
samples = new CircularList<float>(numSamples);
total = 0;
}
/// <summary>
/// Adds a sample to the sample collection.
/// </summary>
public void AddSample(float val)
{
if (samples.Count == samples.Length)
{
total -= samples.Value;
}
samples.Value = val;
total += val;
samples.Next();
}
/// <summary>
/// Clears all samples to 0.
/// </summary>
public void ClearSamples()
{
total = 0;
samples.Clear();
}
/// <summary>
/// Initializes all samples to the specified value.
/// </summary>
public void InitializeSamples(float v)
{
samples.SetAll(v);
total = v * samples.Length;
}
}
}
用法
一个简单的程序演示了 SimpleMovingAverage 类的用法是
using System;
using Clifton.Collections.Generic;
using Clifton.Tools.Data;
namespace AveragerTest
{
class Program
{
static void Main(string[] args)
{
IMovingAverage avg = new SimpleMovingAverage(10);
Test(avg);
}
static void Test(IMovingAverage avg)
{
for (int i = 0; i < 20; i++)
{
avg.AddSample(i);
Console.WriteLine(avg.Average);
}
}
}
}
请注意，样本大小是 10 个项目，但有 20 个样本被添加到移动平均值中。旧样本在添加新样本时被替换。正如代码所示，创建了一个 SimpleMovingAverage 实例并用于初始化变量 avg，其类型为 IMovingAverage。Test 方法将接口作为参数。如果我们实现了，例如，一个 WeightedMovingAverage 类，我们可以将构造更改为
IMovingAverage avg = new WeightedMovingAverage(10);
并调用完全相同的 Test 例程来查看新的移动平均值如何工作。通过使用接口，我们提高了代码的可用性。
所有这些工作！
诚然，对于一个简单的算法来说，这需要大量的工作。就个人而言，我试图遵循尽职尽责的原则，即使是一件小事，因为小事很快就会变成大事。老借口“我们没有时间和预算”，或者“这很简单，赶紧写出来，我们以后再重构”一次又一次地被证明是谎言。先做错并不会节省时间和金钱！重构很少被放入“新”预算中。不良做法会一直持续下去，除非从一开始就加以改变。写出算法的唯一理由是为了原型，这样您就可以从中学习并正确开发生产算法。
历史
- 2007 年 3 月 4 日：初始版本