c - C中的滚动中值算法

Question

我目前正在研究一种用 C 语言实现滚动中值滤波器(类似于滚动均值滤波器)的算法。根据我对文献的搜索，似乎有两种相当有效的方法可以做到这一点。第一种是对值的初始窗口进行排序，然后执行二进制搜索以在每次迭代中插入新值并删除现有值。

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

这是我的问题:实现前者是可行的，但我需要在数百万个时间序列上运行它，所以效率很重要。后者被证明很难实现。我在 R 的统计包代码的 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

Answer 1

我看过 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 代码这可能是窗口方法的合适起点。