可能重复:
C中的滚动中值算法
鉴于从数据流中读取整数.到目前为止,以有效的方式查找元素的中位数.
解决方案我已经读过:我们可以使用左侧的最大堆来表示小于有效中位数的元素,在右侧使用最小堆来表示大于有效中位数的元素.
在处理传入元素之后,堆中元素的数量最多相差1个元素.当两个堆包含相同数量的元素时,我们发现堆的根数据的平均值为有效中值.当堆不平衡时,我们从包含更多元素的堆的根中选择有效中值.
但是我们如何构建最大堆和最小堆,即我们如何知道这里的有效中位数呢？我认为我们会在max-heap中插入1个元素,然后在min-heap中插入下一个元素,依此类推所有元素.纠正我如果我错在这里.
我目前正致力于在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
给定一系列数据(可能有重复数据),固定大小的移动窗口,从数据序列的开始每次迭代移动窗口,以便(1)从窗口中移除最旧的数据元素并且新的数据元素被推入窗口(2)在每次移动时找到窗口内数据的中值.
以下帖子没有帮助.
我的想法:
使用2堆来保持中位数.在窗口旁边,在第一次迭代中对窗口中的数据进行排序,最小堆保存较大的部分,最大堆保存较小的部分.如果窗口具有奇数个数据,则最大堆返回中值,否则两个堆的顶部元素的算术平均值是中值.
将新数据推入窗口时,从其中一个堆中删除最旧的数据,并将新数据与max和min堆的顶部进行比较,以便确定要将数据放入哪个堆.然后,找到中间值就像在第一次迭代中一样.
但是,如何在堆中查找数据元素是一个问题.堆是二叉树而不是二叉搜索树.
是否有可能用O(n)或O(n*lg m)求解它,其中m是窗口大小和空间:O(1)？
任何帮助都非常感谢.
谢谢
我在2D中值滤波器(3x3窗口)中存在瓶颈,我在一组非常大的图像上使用,我想尝试优化它.我测试过scipy.ndimagemedian_filter,以及PIL,scipy.signal和scikits-image.然而,浏览SO我已经知道C中有一个快速的O(n)中值滤波器(恒定时间中的中值滤波,参见C中的滚动中值算法),我想知道我是否可以使用scipy在Python中实现它. weave.inline？有关替代路线的任何建议吗？