LINQ для расчета скользящего среднего из SortedList

Question

У меня есть временной ряд в виде SortedList<dateTime,double>.Я хотел бы рассчитать скользящее среднее из этой серии.Я могу сделать это, используя простые циклы 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<DateTime, double>();
            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<DateTime, double> MovingAverage(SortedList<DateTime, double> series, int period)
        {
            var result = new SortedList<DateTime, double>();

            for (int i = 0; i < series.Count(); i++)
            {
                if (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;
        }
    }
}

Answer 1

Чтобы достичь асимптотической производительности O (n) (как это делает решение с ручным кодированием), вы можете использовать функцию Aggregate, как в

series.Skip(period-1).Aggregate(
  new {
    Result = new SortedList<DateTime, double>(), 
    Working = List<double>(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) элементов в начале)

В функциональном программировании это типичный шаблон использования для совокупной (или fold) функции, кстати.

Два замечания:

Решение не является "функционально" чистым в том смысле, что одни и те же объекты списка (Working и Result) повторно используются на каждом шаге. Я не уверен, что это может вызвать проблемы, если некоторые будущие компиляторы попытаются распараллелить функцию Aggregate автоматически (с другой стороны, я также не уверен, если это все-таки возможно ...). Чисто функциональное решение должно «создавать» новые списки на каждом этапе.

Также обратите внимание, что в C # отсутствуют мощные выражения списка. В некотором гипотетическом псевдокоде, смешанном с Python-C #, можно написать функцию агрегирования, например

(list, item)=>
  new {
    Result = list.Result + [(item.Key, (list.Working+[item.Value]).Average())], 
    Working=list.Working[1::]+[item.Value]
  }

что было бы немного более элегантно, по моему скромному мнению :) 1033 *

Answer 2

Для наиболее эффективного способа , позволяющего вычислить скользящее среднее с 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; } }
}

Этот класс обеспечивает очень быструю и легкую реализацию фильтра MovingAverage. Он создает циклический буфер длины N и вычисляет одно сложение, одно вычитание и одно умножение на каждую добавленную точку данных, в отличие от N умножения-сложения на точку для реализации методом грубой силы.

Далее, к LINQ-ify it!

internal static class MovingAverageExtensions
{
    public static IEnumerable<double> MovingAverage<T>(this IEnumerable<T> inputStream, Func<T, double> selector, int period)
    {
        var ma = new MovingAverage(period);
        foreach (var item in inputStream)
        {
            ma.Push(selector(item));
            yield return ma.Current;
        }
    }

    public static IEnumerable<double> MovingAverage(this IEnumerable<double> 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<double> inputDoubles;
IEnumerable<double> outputDoubles = inputDoubles.MovingAverage(period);   

// Or, use a selector to filter T into a list of doubles
IEnumerable<Point> inputPoints; // assuming you have initialised this
IEnumerable<double> smoothedYValues = inputPoints.MovingAverage(pt => pt.Y, period);

Answer 3

Этот блок

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 .

Answer 4

У вас уже есть ответ, показывающий, как вы можете использовать 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.

Answer 5

Чтобы сделать это более функциональным способом, вам понадобится метод Scan, который существует в Rx, но отсутствует в LINQ.

Давайте посмотрим, как бы выглядело, если бы у нас был метод сканирования

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<TAccumulate> Scan<TSource, TAccumulate>(
    this IEnumerable<TSource> source,
    TAccumulate seed,
    Func<TAccumulate, TSource, TAccumulate> 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. Затем каждое последующее значение мы рассчитываем из накопленного начального значения. Для этого нам понадобится старое значение (т. Е. Дельта) и новейшее значение, для которого мы сшиваем ряды, один раз от начала и один раз смещенные дельтой.

В конце мы делаем некоторую очистку, добавляя нули для длины первого периода и добавляя начальное начальное значение.

Answer 6

Другой вариант - использовать метод MoreLINQ * Windowed, который значительно упрощает код:

var averaged = mySeries.Windowed(period).Select(window => window.Average(keyValuePair => keyValuePair.Value));

Answer 7

Я использую этот код для расчета 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<decimal, decimal> SMA(int p)
{
    Queue<decimal> s = new Queue<decimal>(p);
    return (x) =>
    {
        if (s.Count >= p)
        {
            s.Dequeue();
        }
        s.Enqueue(x);
        return s.Average();
    };
}