c - C语言中的滚动中值算法

我目前正在研究一种算法，以在C语言中实现滚动中值过滤器(类似于滚动均值过滤器)。根据我对文献的搜索，似乎有两种合理有效的方法可以执行此操作。首先是对值的初始窗口进行排序，然后执行二进制搜索以插入新值，并在每次迭代时都删除现有值。

第二种方法(来自Hardle和Steiger，1995年，JRSS-C，算法296)构建了一个双端堆结构，一端为maxheap，另一端为minheap，中间为中值。这产生了线性时间算法，而不是O(n log n)。

这是我的问题:实现前者是可行的，但是我需要在数百万个时间序列上运行它，因此效率非常重要。事实证明，后者非常难以实现。我在R的stats软件包的代码的Trunmed.c文件中找到了代码，但这是相当难以理解的。

有人知道线性时间滚动中值算法的编写良好的C实现吗？

编辑:链接到Trunmed.c代码http://google.com/codesearch/p?hl=en&sa=N&cd=1&ct=rc#mYw3h_Lb_e0/R-2.2.0/src/library/stats/src/Trunmed.c

最佳答案

我已经看过R的src/library/stats/src/Trunmed.c了几次，因为我也希望在独立的C++类/ C子例程中也有类似的东西。请注意，这实际上是两种实现，请参阅src/library/stats/man/runmed.Rd(帮助文件的源代码)，其中说

\details{
  Apart from the end values, the result \code{y = runmed(x, k)} simply has
  \code{y[j] = median(x[(j-k2):(j+k2)])} (k = 2*k2+1), computed very
  efficiently.

  The two algorithms are internally entirely different:
  \describe{
    \item{"Turlach"}{is the Härdle-Steiger
      algorithm (see Ref.) as implemented by Berwin Turlach.
      A tree algorithm is used, ensuring performance \eqn{O(n \log
        k)}{O(n * log(k))} where \code{n <- length(x)} which is
      asymptotically optimal.}
    \item{"Stuetzle"}{is the (older) Stuetzle-Friedman implementation
      which makes use of median \emph{updating} when one observation
      enters and one leaves the smoothing window.  While this performs as
      \eqn{O(n \times k)}{O(n * k)} which is slower asymptotically, it is
      considerably faster for small \eqn{k} or \eqn{n}.}
  }
}

很高兴看到它以更独立的方式被重新使用。你在自愿吗？我可以帮助一些R位。

编辑1:除了上面指向Trunmed.c的旧版本的链接之外，这是当前的SVN副本

Srunmed.c (适用于Stuetzle版本)

Trunmed.c (对于Turlach版本)

runmed.R 用于R函数，调用这些

编辑2:Ryan Tibshirani在fast median binning上有一些C和Fortran代码，这可能是开窗方法的合适起点。

关于c - C语言中的滚动中值算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1309263/