C++有效地计算运行中位数
Edg*_*dge 25 c++ algorithm median
那些读过我之前问题的人都知道我在理解和实现快速排序和快速选择方面的工作,以及其他一些基本算法.
Quickselect用于计算未排序列表中的第k个最小元素,此概念也可用于查找未排序列表中的中位数.
这一次,我需要帮助设计一种有效的技术来计算运行中位数,因为快速选择不是一个好的选择,因为它需要在每次列表更改时重新计算.因为quickselect必须每次都重新启动,所以它不能利用先前的计算,所以我正在寻找一种类似(可能)但在运行中位数方面更有效的不同算法.
use*_*810 44
该流中位数是用两个堆计算.小于或等于当前中位数的所有数字都在左堆中,其排列使得最大数量位于堆的根处.所有大于或等于当前中位数的数字都在右侧堆中,其排列使得最小数量位于堆的根部.请注意,等于当前中位数的数字可以在任一堆中.两个堆中的数字计数从不相差超过1.
当过程开始时,两个堆最初是空的.输入序列中的第一个数字被添加到其中一个堆中,哪个并不重要,并作为第一个流中位数返回.然后输入序列中的第二个数字被添加到另一个堆中,如果右堆的根小于左堆的根,则交换两个堆,并且这两个数的平均值作为第二个流返回中位数.
然后主算法开始.输入序列中的每个后续数字与当前中位数进行比较,如果小于当前中位数,则添加到左侧堆中;如果大于当前中位数,则添加到右侧堆中; 如果输入数字等于当前中位数,则将其添加到具有较小计数的任何堆中,或者如果它们具有相同计数则任意堆积.如果这导致两个堆的计数差异超过1,则删除较大堆的根并将其插入较小的堆中.然后将当前中位数计算为较大堆的根,如果它们的计数不同,或者两个堆的根的平均值(如果它们是相同的大小).
Scheme和Python中的代码可以在我的博客上找到.
- 向系统添加元素是可以的.但是如何删除旧元素呢？ (3认同)
Jef*_*ock 16
杰夫麦克林托克运行中位数估计.只需要保留两个值.此示例迭代一组采样值(CPU消耗).似乎相对较快地收敛(约100个样本)到中位数的估计.该想法是在每次迭代时以恒定速率朝向输入信号的中值英寸.该比率取决于您估计中位数的幅度.我使用平均值作为中位数幅度的估计值,以确定中位数每个增量的大小.如果您的中位数精确到约1%,请使用0.01*平均值的步长.
float median = 0.0f;
float average = 0.0f;
// for each sample
{
average += ( sample - average ) * 0.1f; // rough running average.
median += _copysign( average * 0.01, sample - median );
}
- 尽管此解决方案非常有效，但是请注意以下警告：1）收敛速度取决于信号幅度（比较具有不同偏移量和幅度的阶跃响应），因此不会针对接近零的信号收敛！2）对于接近恒定的输入信号，此估计会引入幅度为“平均值* 0.01”且采样频率为3的抖动。3）在短脉冲时会偏斜（最初没有中值，因此流行为胡椒和噪声滤波器） (2认同)