C # Расчет скользящей медианы временных рядов SortedList- улучшить производительность?

Question

У меня есть метод, который вычисляет значение скользящей медианы временного ряда.Как скользящая средняя, ​​она использует фиксированное окно или период (иногда называемый периодом оглядки назад).Если период равен 10, будет создан массив из первых 10 значений (0-9), а затем найдется их среднее значение.Это будет повторяться, увеличивая окно на 1 шаг (значения 1-10 сейчас) и так далее ... отсюда и движущаяся часть этого.Этот процесс точно такой же, как скользящее среднее.

Значение медианы находится следующим образом:

1. Сортировка значений массива
2. Если в массиве нечетное количество значений, взять среднее значение,Медиана отсортированного массива из 5 значений будет 3-м значением.
3. Если в массиве есть четное число значений, возьмите два значения с каждой стороны от среднего и усредните их.Медиана отсортированного массива из 6 значений будет (2-й + 3-й) / 2.

Я создал функцию, которая вычисляет это путем заполнения List<double>, вызова List<>.Sort() изатем найти подходящие значения.

Вычислительный это правильно, но мне было интересно, если есть способ улучшить производительность этого расчета.Возможно, путем ручной сортировки double[] вместо использования списка.

Моя реализация выглядит следующим образом:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Moving_Median_TimeSeries
{
    class Program
    {
        static void Main(string[] args)
        {
            // created a a sample test time series of 10 days
            DateTime Today = DateTime.Now;
            var TimeSeries = new SortedList<DateTime, double>();
            for (int i = 0; i < 10; i++)
                TimeSeries.Add(Today.AddDays(i), i * 10);

            // write out the time series
            Console.WriteLine("Our time series contains...");
            foreach (var item in TimeSeries) 
                Console.WriteLine("   {0}, {1}", item.Key.ToShortDateString(), item.Value);

            // calculate an even period moving median 
            int period = 6;
            var TimeSeries_MovingMedian = MovingMedian(TimeSeries, period);

            // write out the result of the calculation
            Console.WriteLine("\nThe moving median time series of {0} periods contains...", period);
            foreach (var item in TimeSeries_MovingMedian)
                Console.WriteLine("   {0}, {1}", item.Key.ToShortDateString(), item.Value);

            // calculate an odd period moving median 
            int period2 = 5;
            var TimeSeries_MovingMedian2 = MovingMedian(TimeSeries, period);

            // write out the result of the calculation
            Console.WriteLine("\nThe moving median time series of {0} periods contains...", period2);
            foreach (var item in TimeSeries_MovingMedian2)
                Console.WriteLine("   {0}, {1}", item.Key.ToShortDateString(), item.Value);
        }

        public static SortedList<DateTime, double> MovingMedian(SortedList<DateTime, double> TimeSeries, int period)
        {
            var result = new SortedList<DateTime, double>();

            for (int i = 0; i < TimeSeries.Count(); i++)
            {
                if (i >= period - 1)
                {
                    // add all of the values used in the calc to a list... 
                    var values = new List<double>();
                    for (int x = i; x > i - period; x--)
                        values.Add(TimeSeries.Values[x]);

                    // ... and then sort the list <- there might be a better way than this
                    values.Sort();

                    // If there is an even number of values in the array (example 10 values), take the two mid values
                    // and average them.  i.e. 10 values = (5th value + 6th value) / 2. 
                    double median;
                    if (period % 2 == 0) // is any even number
                        median = (values[(int)(period / 2)] + values[(int)(period / 2 - 1)]) / 2;
                    else // is an odd period
                    // Median equals the middle value of the sorted array, if there is an odd number of values in the array
                        median = values[(int)(period / 2 + 0.5)];

                    result.Add(TimeSeries.Keys[i], median);
                }
            }
            return result;
        }

    }
}

Answer 1

Для списка из N элементов и периода P ваш алгоритм, который пересортирует список для каждого элемента, равен O (N * P lgP). Существует алгоритм O (N * lg P), который использует 2 кучи .

Используется минимальная куча, содержащая элементы P / 2 выше медианы, и максимальная куча, в которой элементы P-P / 2 меньше или равны ей. Всякий раз, когда вы получаете новый элемент данных, замените самый старый элемент новым, затем сделайте sift-up или sift-down, чтобы переместить его в нужное место. Если новый элемент достигает корня любой кучи, сравните его с корнем другого и поменяйте местами при необходимости. Для нечетного P медиана находится в корне max-heap. Для четного P это среднее от обоих корней.

В этом вопросе есть c реализация . Одним из сложных моментов в его реализации является эффективное отслеживание самого старого элемента. Издержки в этой части могут сделать прирост скорости незначительным для малых P.

Answer 2

может быть лучший способ, чем этот

Вы правы в этом - вам не нужно сортировать весь список, если все, что вы хотите, это медиана.Перейдите по ссылкам со этой страницы википедии , чтобы узнать больше.