LINQ计算SortedList的移动平均值
我有一个SortedList
forms的时间序列。 我想计算一下这个系列的移动平均线。 我可以使用简单的for循环来做到这一点。 我想知道是否有更好的方法来使用linq。
我的版本:
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { var mySeries = new SortedList(); mySeries.Add(new DateTime(2011, 01, 1), 10); mySeries.Add(new DateTime(2011, 01, 2), 25); mySeries.Add(new DateTime(2011, 01, 3), 30); mySeries.Add(new DateTime(2011, 01, 4), 45); mySeries.Add(new DateTime(2011, 01, 5), 50); mySeries.Add(new DateTime(2011, 01, 6), 65); var calcs = new calculations(); var avg = calcs.MovingAverage(mySeries, 3); foreach (var item in avg) { Console.WriteLine("{0} {1}", item.Key, item.Value); } } } class calculations { public SortedList MovingAverage(SortedList series, int period) { var result = new SortedList(); for (int i = 0; i = period - 1) { double total = 0; for (int x = i; x > (i - period); x--) total += series.Values[x]; double average = total / period; result.Add(series.Keys[i], average); } } return result; } } }
您已经有一个答案向您展示如何使用LINQ,但坦率地说,我不会在这里使用LINQ,因为与您当前的解决方案相比,它很可能表现不佳,而您现有的代码已经很清楚了。
但是,不是计算每个步骤中前一个period
元素的总和,而是可以保持运行总计并在每次迭代时进行调整。 也就是说,改变这个:
total = 0; for (int x = i; x > (i - period); x--) total += series.Values[x];
对此:
if (i >= period) { total -= series.Values[i - period]; } total += series.Values[i];
这意味着无论period
大小如何,您的代码都将花费相同的时间执行。
为了实现O(n)的渐近性能(如手工编码解决方案所做的那样),您可以使用Aggregate
函数,如
series.Skip(period-1).Aggregate( new { Result = new SortedList(), Working = List(series.Take(period-1).Select(item => item.Value)) }, (list, item)=>{ list.Working.Add(item.Value); list.Result.Add(item.Key, list.Working.Average()); list.Working.RemoveAt(0); return list; } ).Result;
累积值(以匿名类型实现)包含两个字段: Result
包含到目前为止构建的结果列表。 Working
包含最后一个period-1
元素。 聚合函数将当前值添加到工作列表,构建当前平均值并将其添加到结果中,然后从工作列表中删除第一个(即最旧的)值。
通过将第一个period-1
元素放入Working
并将Result
初始化为空列表来构建“种子”(即累积的起始值)。
因此,聚合从元素period
开始(通过在开头跳过(period-1)
元素)
在函数式编程中,这是aggretate(或fold
)函数的典型使用模式,顺便说一句。
两个评论:
解决方案不是“function性”清洁,因为在每个步骤中都会重复使用相同的列表对象( Working
和Result
)。 如果未来的某些编译器试图自动并行化Aggregate函数,我不确定这是否会引起问题(另一方面,我也不确定,如果可能的话……)。 纯function解决方案应该在每一步“创建”新列表。
另请注意,C#缺少强大的列表表达式。 在一些假设的Python-C#混合伪代码中,可以编写聚合函数
(list, item)=> new { Result = list.Result + [(item.Key, (list.Working+[item.Value]).Average())], Working=list.Working[1::]+[item.Value] }
在我的拙见:)这会更优雅:)
为了使用LINQ计算移动平均线的最有效方法 ,您不应该使用LINQ!
相反,我建议创建一个辅助类,以尽可能最有效的方式计算移动平均值 (使用循环缓冲区和因果移动平均滤波器), 然后使用扩展方法使LINQ可以访问它。
首先是移动平均线
public class MovingAverage { private readonly int _length; private int _circIndex = -1; private bool _filled; private double _current = double.NaN; private readonly double _oneOverLength; private readonly double[] _circularBuffer; private double _total; public MovingAverage(int length) { _length = length; _oneOverLength = 1.0 / length; _circularBuffer = new double[length]; } public MovingAverage Update(double value) { double lostValue = _circularBuffer[_circIndex]; _circularBuffer[_circIndex] = value; // Maintain totals for Push function _total += value; _total -= lostValue; // If not yet filled, just return. Current value should be double.NaN if (!_filled) { _current = double.NaN; return this; } // Compute the average double average = 0.0; for (int i = 0; i < _circularBuffer.Length; i++) { average += _circularBuffer[i]; } _current = average * _oneOverLength; return this; } public MovingAverage Push(double value) { // Apply the circular buffer if (++_circIndex == _length) { _circIndex = 0; } double lostValue = _circularBuffer[_circIndex]; _circularBuffer[_circIndex] = value; // Compute the average _total += value; _total -= lostValue; // If not yet filled, just return. Current value should be double.NaN if (!_filled && _circIndex != _length - 1) { _current = double.NaN; return this; } else { // Set a flag to indicate this is the first time the buffer has been filled _filled = true; } _current = _total * _oneOverLength; return this; } public int Length { get { return _length; } } public double Current { get { return _current; } } }
此类提供了一个非常快速且轻量级的MovingAveragefilter实现。 它创建一个长度为N的循环缓冲区,并计算每附加一个数据点的一个加法,一个减法和一个乘法,而不是powershell实现的每个点的N乘法加法。
接下来,到LINQ-ify吧!
internal static class MovingAverageExtensions { public static IEnumerable MovingAverage(this IEnumerable inputStream, Func selector, int period) { var ma = new MovingAverage(period); foreach (var item in inputStream) { ma.Push(selector(item)); yield return ma.Current; } } public static IEnumerable MovingAverage(this IEnumerable inputStream, int period) { var ma = new MovingAverage(period); foreach (var item in inputStream) { ma.Push(item); yield return ma.Current; } } }
上述扩展方法包装MovingAverage类,并允许插入IEnumerable流。
现在用它!
int period = 50; // Simply filtering a list of doubles IEnumerable inputDoubles; IEnumerable outputDoubles = inputDoubles.MovingAverage(period); // Or, use a selector to filter T into a list of doubles IEnumerable inputPoints; // assuming you have initialised this IEnumerable smoothedYValues = inputPoints.MovingAverage(pt => pt.Y, period);
这个街区
double total = 0; for (int x = i; x > (i - period); x--) total += series.Values[x]; double average = total / period;
可以改写为:
double average = series.Values.Skip(i - period + 1).Take(period).Sum() / period;
您的方法可能如下所示:
series.Skip(period - 1) .Select((item, index) => new { item.Key, series.Values.Skip(index).Take(period).Sum() / period });
如你所见,linq非常富有表现力。 我建议从一些教程开始,比如介绍LINQ和101 LINQ Samples 。
要以更实用的方式执行此操作,您需要一个存在于Rx但不存在于LINQ中的Scan
方法。
让我们来看看如果我们有扫描方法会是什么样子
var delta = 3; var series = new [] {1.1, 2.5, 3.8, 4.8, 5.9, 6.1, 7.6}; var seed = series.Take(delta).Average(); var smas = series .Skip(delta) .Zip(series, Tuple.Create) .Scan(seed, (sma, values)=>sma - (values.Item2/delta) + (values.Item1/delta)); smas = Enumerable.Repeat(0.0, delta-1).Concat(new[]{seed}).Concat(smas);
这是扫描方法,从这里采取和调整:
public static IEnumerable Scan( this IEnumerable source, TAccumulate seed, Func accumulator ) { if (source == null) throw new ArgumentNullException("source"); if (seed == null) throw new ArgumentNullException("seed"); if (accumulator == null) throw new ArgumentNullException("accumulator"); using (var i = source.GetEnumerator()) { if (!i.MoveNext()) { throw new InvalidOperationException("Sequence contains no elements"); } var acc = accumulator(seed, i.Current); while (i.MoveNext()) { yield return acc; acc = accumulator(acc, i.Current); } yield return acc; } }
这应该比蛮力方法具有更好的性能,因为我们使用运行总计来计算SMA。
这里发生了什么?
首先,我们需要计算我们称之为seed
的第一个时期。 然后,我们从累积的种子值计算每个后续值。 要做到这一点,我们需要旧的值(即t-delta)和我们将系列压缩在一起的最新值,一次从开始,一次移动三角洲。
最后,我们通过在第一个周期的长度上添加零并添加初始种子值来进行一些清理。
另一种选择是使用MoreLINQ的Windowed
方法,它可以显着简化代码:
var averaged = mySeries.Windowed(period).Select(window => window.Average(keyValuePair => keyValuePair.Value));
我用这段代码来计算SMA:
private void calculateSimpleMA(decimal[] values, out decimal[] buffer) { int period = values.Count(); // gets Period (assuming Period=Values-Array-Size) buffer = new decimal[period]; // initializes buffer array var sma = SMA(period); // gets SMA function for (int i = 0; i < period; i++) buffer[i] = sma(values[i]); // fills buffer with SMA calculation } static Func SMA(int p) { Queue s = new Queue (p); return (x) => { if (s.Count >= p) { s.Dequeue(); } s.Enqueue(x); return s.Average(); }; }