C 中的滚动中值算法

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

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

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

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

编辑：链接到 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 位问题。

Edit 1：除了上面旧版本 Trunmed.c 的链接之外，这里还有当前的 SVN 副本

• Srunmed.c（适用于 Stuetzle 版本）
• Trunmed.c（针对图拉赫版本）
• runmed.R对于调用这些的 R 函数

Edit 2：Ryan Tibshirani 有一些 C 和 Fortran 代码快速中值合并这可能是窗口方法的合适起点。