C#如何计算时间序列SortedList<DateTime,double>的移动中位数以提高性能？

Question

我有一个计算时间序列移动中位数的方法。与移动平均值一样，它使用固定的窗口或周期（有时称为回溯期）。 如果周期是10，则会创建一个由前10个值（0-9）组成的数组，然后找到它们的中位数。它将重复这个过程，每次将窗口增加1步（现在是值1-10），等等...因此这就是移动的部分。这个过程与移动平均值完全相同。

中位数通过以下方式找到：

1. 对数组的值进行排序 2. 如果数组中有奇数个值，请取中间值。5个值的排序数组的中位数将是第3个值。 3. 如果数组中有偶数个值，请取中间两边的两个值并求平均值。6个值的排序数组的中位数将是(第2个+第3个)/2。

我创建了一个函数来通过填充List、调用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;
        }

    }
}

- Andre P.

---

只有在真正需要优化时才进行优化。除此之外，我看到的唯一一件事是你可以在循环外创建一个具有所需容量的值列表，但我不认为它会给你带来更好的速度，只是看起来更好而已。 - ba__friend

Answer 1

对于一个包含N个项目和周期P的列表，每个项目重新排序的算法是O(N * P lgP)。有一种O(N * lg P)的算法，它使用了2个堆。

它使用一个最小堆，其中包含中位数以上的P/2个项目，以及一个最大堆，其中包含小于或等于中位数的P-P/2个项目。每当您获得一个新的数据项时，用新项替换最旧的项，然后进行筛选上移或下移以将其移动到正确的位置。如果新项到达任一堆的根部，请将其与另一个堆的根进行比较，并在需要时进行交换和筛选下移。对于奇数P，中位数位于最大堆的根部。对于偶数P，它是两个根的平均值。

这里有一个C语言实现。实现中的一个棘手部分是有效地跟踪最旧的项目。该部分的开销可能使小P的速度增益无关紧要。

- AShelly

Answer 2

可能有比这更好的方法

你说得对 - 如果你只想要中位数，那么你不需要对整个列表进行排序。请从这个维基百科页面查看更多信息。

- AakashM