高效计算运行中值[副本]

Question

读过我之前问题的人都知道我在理解和实现快速排序和快速选择以及其他一些基本算法方面的工作。

Quickselect用于计算未排序列表中的第k个最小元素，这个概念也可以用于寻找未排序列表中的中值。

这一次，我需要帮助来设计一种有效的技术来计算运行中位数，因为快速选择不是一个好的选择，因为它需要在每次列表更改时重新计算。因为快速选择每次都必须重新启动，所以它不能利用之前完成的计算，所以我正在寻找一种不同的算法，它可能类似（可能），但在运行中位数方面更有效。

Answer 1

一种解决方案是维护一个顺序统计树，依次插入序列的每个元素，然后计算树中元素的中位数。

这将花费每次插入O(lg n)时间和每个中值O(lg n)时间，总共O(n lg n)时间，加上O(n)空间。

Answer 2

杰夫·麦克林托克（Jeff McClintock）运行中位数估计。只需要保留两个值。此示例循环访问采样值数组（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 );
}

Answer 3

使用两个堆来计算流中值。所有小于或等于当前中值的数字都在左堆中，其排列方式使得最大数位于堆的根。所有大于或等于当前中值的数字都在右堆中，其排列方式使得最小的数字位于堆的根。请注意，等于当前中值的数字可以在任一堆中。两个堆中的数字计数相差不会超过1。

当进程开始时，两个堆最初是空的。输入序列中的第一个数字被添加到其中一个堆中，不管是哪个，并作为第一个流中位数返回。然后将输入序列中的第二个数字添加到另一个堆中，如果右堆的根小于左堆的根，则交换两个堆，并将两个数字的平均值作为第二个流中位数返回。

然后主算法开始。将输入序列中的每个后续数字与当前中值进行比较，如果小于当前中值，则添加到左侧堆中，如果大于当前中值，则添加到右侧堆中；如果输入数等于当前中值，则将其添加到计数较小的堆中，或者添加到计数相同的任意堆中。如果这导致两个堆的计数相差超过1，则较大堆的根将被移除并插入较小堆中。然后，如果两个堆的数量不同，则将当前中值计算为较大堆的根；如果两个堆的大小相同，则将当前中值计算为两个堆的根的平均值。

Scheme和Python中的代码可以在我的博客上找到。