说,如果我有一个最终的数字数组,请说:
{1, 5, 7, 2}
他们的平均值为:
(1 + 5 + 7 + 2) / 4; //Or, sum of all elements, divided by their number
但是,如果我的数组在不断增长,并且我需要知道当前的平均数,而此时整个数组还不知道。你是怎么计算的?
比如说,当我试图显示当前的数据传输速率时。
每次您获得一个新值时,都会更新您的总和和计数,并在需要向用户显示它们时简单地将两者相除。
但是,对于数据传输率,这是有问题的方法。想一想您开始使用高带宽传输然后连接断开的场景,使用简单的平均值可能需要很长时间才能让您的 UI 反映当前传输速率为 0。使用加权移动平均是一种快速方法使您的 UI 看起来更具响应性。
最简单的实现是定期(比如每 5 秒)对传输速率进行采样,并使用以下方法计算您的速率:
float weight = 2.0; //you are going to want to tweak this to get the right balance between "responsive" and "noisy"
void UpdateAverage(float newValue)
{
this.Average = (this.Average + (newValue*weight))/(weight+1)
}
我会采用一种简单的方法来获得具有running total
恒定空间复杂度(1)的(累积)。并根据 avg 的要求,返回结果为 running total/total number of item
. 没有延长时间复杂度,因为我们不会在之后迭代数组来找到累积和。
我知道我在这里聚会迟到了,但我在 2000 年解决了一个类似的问题,当时我正在创建一个自适应负载平衡器。标准平均值有两个问题,都在给出的答案中提到:
因此,您可以将正常平均值计算转换为数学家所说的“递归关系”,这意味着您存储以前的平均值,然后用于计算新的平均值(类似于 Yaur 的答案,我必须同意 ahmed,我看不出它被否决了)。那天我在 Delphi 中编写了原件,所以我最近在 .NET 中再次做了同样的事情,并将其与随着项目列表变大而计算连续平均值的标准过程进行了比较。
不想自我推销(我发布链接只是为了节省我的打字手指),您可以在以下位置找到理论处理、代数、比较实验的结果以及它如何解决问题:
http://goadingtheitgeek.blogspot.co.uk/2014/05/blast-from-past.html
希望对你有帮助。
您正在寻找移动平均线:
static void Main(string[] args) {
var nums = Enumerable.Range(1, 5).Select(n => (double)n);
nums = nums.Concat(nums.Reverse());
var sma3 = SMA(3);
var sma5 = SMA(5);
foreach (var n in nums) {
Console.WriteLine("{0} (sma3) {1,-16} (sma5) {2,-16}", n, sma3(n), sma5(n));
}
}
static Func<double, double> SMA(int p) {
Queue<double> s = new Queue<double>(p);
return (x) => {
if (s.Count >= p) {
s.Dequeue();
}
s.Enqueue(x);
return s.Average();
};
}
资料来源:http ://rosettacode.org/wiki/Averages/Simple_moving_average#C.23
我敢打赌,你想要一些快速的东西,否则你已经有了答案。将您已经拥有的所有数字与您已经拥有的数组的长度相加。这非常简单。
但是有时您无法知道数组是否有界,它可能是无限的,例如来自麦克风的数据。在这种情况下,移动平均线的建议很好,这意味着您必须从数组中获取最后的 x 值并仅计算这些值的平均值。无论您有 x 值还是 1000x 值,计算结果所需的算法和时间都保持不变。
编辑 :
x vs 1000x 来自算法复杂性。假设您将 5 个数字相加,即 5 次运算,然后除以 5,再进行一次运算,总共 6(为了示例,我们假设它们都花费相同的计算机时间,但实际上除法很慢与添加相比)。如果您使用相同的代码但有 1000 个数字,您将执行 1001 次操作,这将比第一种情况花费更多的时间!
使用“移动平均线”,您始终采用固定数量的数字,因此无论您有 5 个还是 1000 个数字,您的算法都需要固定的时间来执行。
移动平均线只是一种花哨的措辞,表示您不会在数组中从一次到另一次取相同的数字。想象一下以下数组:
int x = { 1, 4, 6, 3, 1 };
int arrayLength = 5;
那么这个数组的平均值将是
int runningTotal = 0;
for(int i = 0; i < arrayLength; i++)
{
runningTotal += x[i];
}
double average = runningTotal / arrayLength
3个值的移动平均值将是
int movingLength = 3;
int runningTotal = 0;
for(int i = 0; i < movingLength; i++)
{
runningTotal += x[arrayLength - i - 1];
}
double average = runningTotal / movingLength;
因此,当数组增长时,数组中的第一个值不是计算的一部分。
假设你不想要移动平均线..
上次计算平均值时,您需要跟踪元素的当前总和。
如果你的数组是这个......
Array = {1, 5, 7, 2}
Sum = 1 + 5 + 7 + 2 = 15
Number of elements = 4
Average = Sum / Number of elements = 3.75
你添加了几个元素,你的数组看起来像这样......
Array = {1, 5, 7, 2, 10, 6}
假设您的实际数组要大得多...重新计算您的平均值..
Sum = ([previous sum] + [sum of new elements]) / [number of elements]
Number of elements = 6
Average = ((15 * 4) + 10 + 6) / 6 = 5.1666667
编辑:如果您担心精度和大小,请查看BigInteger
如果平均缓冲区长度是可变的,我的旧程序就是这样。
namespace WindowsFormsApplication1
{
public partial class ComTester : Form
{
public int []sAvgArr=new int [251];
public int sAvgAdr,sAvgCnt;
private void Calc_Values(object sender, int v)//v is value
{
int n = AverageLength;
if (n > 250) n = 250;//average buffer maksimum
if (n > 0)
{
sAvgArr[sAvgAdr] = v;
sAvgAdr += 1;
sAvgCnt += 1;
if (n <= sAvgAdr) sAvgAdr = 0;
if (n <= sAvgCnt) sAvgCnt = n;
n = sAvgCnt;
int f = 0, l = 0; ;
for (l = 0; l < n; l += 1)
f += sAvgArr[l];
f = f / sAvgCnt;
sAvgVal = f;
}
else
{
sAvgVal=v;
}
}
}
}
using System;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int n = 3 , x , sum = 0 ;
double ave;
for (int i = 0; i < n; i++ )
{
Console.WriteLine("enter the number:");
x = Convert.ToInt16(Console.ReadLine());
sum += x;
}
ave = (double)(sum) / 3;
Console.WriteLine("average:");
Console.WriteLine( ave );
Console.ReadLine();
}
}
}