C＃计算时间序列的移动中值SortedList <DateTime，double> - 提高性能？

我有一种方法可以计算时间序列的移动中值。就像移动平均值一样，它使用固定的窗口或周期（有时称为回顾期）。如果周期为10，它将创建前10个值（0-9）的数组，然后查找它们的中值。它会重复这一步，将窗口递增1步（现在的值为1-10），等等......因此是这个的移动部分。这个过程与移动平均线完全相同。C＃计算时间序列的移动中值SortedList <DateTime，double> - 提高性能？

中位值由实测值：

对数组排序
的值如果为奇数编号的数组中的值，取中间值。一个有5个值的排序数组的中值将是第3个值。
如果数组中有偶数个值，则取中间每一侧的两个值并对其进行平均。 6个值的排序后的数组的中值将是（第二+第三）/ 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; 
     } 

    } 
}

来源

2011-03-09 Andre P.

只有当您真的需要优化时才会进行优化。除此之外，我唯一看到的是你可以创建一个期望容量的循环外的值列表，但我不认为它会给你一个更好的速度。只是看起来更好。 – 2011-03-09 11:04:06

有可能比一个更好的办法这个

你是对的这一点 - 你不需要排序整个列表，如果所有你想要的是中位数。请点击this wikipedia page以获取更多链接。

来源

2011-03-09 12:14:31 AakashM

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

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

有一个c implementation in this question。实施它的一个棘手部分是有效地跟踪最古老的项目。该部分的开销可能会使速度对小P来说微不足道。

来源

2011-06-20 20:07:46 AShelly

C＃计算时间序列的移动中值SortedList <DateTime，double> - 提高性能？

回答

相关问题