我目前正致力于在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