LINQ для вычисления скользящего среднего SortedList <dateTime, double>

Ответ 1

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

Ответ 2

Чтобы достичь асимптотической производительности 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) в начале)

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

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

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

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

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

который был бы немного более изящным по моему скромному мнению:)

Ответ 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.

Ответ 4

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

Ответ 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 здесь. Затем каждое последующее значение вычисляется по накопленному начальному значению. Для этого нам нужно старое значение (то есть t-дельта) и самое новое значение, для которого мы запишем вместе серию, один раз с самого начала и однажды сдвинутый на дельту.

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

Ответ 6

Я использую этот код для вычисления 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();
    };
}

Ответ 7

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

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