3

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

中值通过以下方式找到：

  1. 对数组的值进行排序
  2. 如果数组中有奇数个值，则取中间值。5 个值的排序数组的中位数将是第三个值。
  3. 如果数组中有偶数个值，则取中间值每一侧的两个值并将它们平均。6 个值的排序数组的中位数是 (2nd + 3rd) / 2。

我创建了一个函数，它通过填充 a 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;
        }

    }
}
4

2 回答 2

0

可能有比这更好的方法

你是对的 - 如果你想要的只是中位数，你不需要对整个列表进行排序。按照此维基百科页面的链接了解更多信息。

于 2011-03-09T12:14:31.930 回答
0

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

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

这个问题有一个c 实现。实现它的一个棘手部分是有效地跟踪最旧的项目。该部分的开销可能会使速度增益对于小 P 来说微不足道。

于 2011-06-20T20:07:46.753 回答