想象一下，您正在应用程序中实现性能遥测。有一个操作执行了数百万次，并且您希望获得其“平均”持续时间。使用算术平均值不是一个好主意，因为获得的值可以很容易地获得被离群值宠坏了。最好使用中位数，这是描述平均值的最可靠方法之一。
简单的中值估计方法需要存储所有值，在我们的案例中，保留所有值是一个坏主意，因为这会显着增加内存占用量，这种遥测是有害的，因为它可能成为新的瓶颈而不是监视实际性能。
获取中位数的另一种方法是使用顺序分位数估计器（也称为在线分位数估计器或流式分位数估计器），该算法允许使用固定量来计算中位数（或任何其他分位数）当然，它仅提供真实中值的近似值，但通常对于典型遥测用例就足够了。
在这篇文章中，我将展示最简单的顺序分位数估计器之一，称为P²分位数估计器（或逐段抛物线分位数估计器）。
该算法最初是在[Jain1985]中提出的。在下面可以找到这种方法的简短概述，原始论文中有关错别字的注释，数值模拟和C＃实现。
假设我们有一个观测流\（\ {x_0，x_1，x_2，x_3，x_4，\ ldots \} \）并且我们想要估计p分位数。建议的方法引入了五个标记，它们对应于
同样，我们必须保持标记位置\（\ {n_0，n_1，n_2，n_3，n_4 \} \）。这些整数值描述了当前获得的观测值的实际标记索引。
接下来，我们必须定义标记的期望位置\（\ {n'_0，n'_1，n'_2，n'_3，n'_4 \} \）。对于第一个\（n \）个观测值，这些实数值定义如下：
为了加快算法的运行速度，我们可以预先计算所需位置的增量，这些增量应在每次新观察后添加到当前值中：
请注意，在原始论文中，作者使用基于1的索引，因此我决定将其改编为基于0的索引，从实现的角度来看更方便。
\ [\ left \ {\ begin {array} {llll} q_0 = x _ {（0）}，＆n_0 = 0，＆n'_0 = 0，＆dn'_0 = 0，\\ q_1 = x _ {（1 ）}，＆n_1 = 1，＆n'_1 = 2p，＆dn'_1 = p / 2，\\ q_2 = x _ {（2）}，＆n_2 = 2，＆n'_2 = 4p，＆dn' _2 = p，\\ q_3 = x _ {（3）}，＆n_3 = 3，＆n'_3 = 2 + 2p，＆dn'_3 =（1 + p）/ 2，\\ q_4 = x _ {（4 ）}，＆n_4 = 4，＆n'_4 = 4，＆dn'_4 =1。\ end {array} \ right。\]
首先，我们应该调整极端标记高度（如果\（x_j q_4 \），我们应该更新\（q_4 \））并找到\（k \ ）使得\（q_k \ leq x_j = 1 && n [i + 1]-n [i]> 1 || d = 1 && n [i + 1]-n [i]> 1 || d <=-1 && n [i-1]-n [i] <-1）{int dInt =数学。签署（d）; double qs =抛物线（i，dInt）;如果（q [i-1] P²分位数估计器允许在不存储单个值的情况下估计数字流中的分位数。还有许多其他顺序分位数估计器，但是从实现的角度来看，P²分位数估计器是最简单的分位数估计器之一。该算法可用于在您的应用程序中引入性能遥测，而不会产生明显的性能或内存占用开销。 [Jain1985] Jain，Raj和Imrich Chlamtac。“用于动态计算分位数和直方图而不存储观测值的P²算法。” ACM通讯28，没有。 10（1985）：1076-1085。 [Hyndman 1996] Hyndman，R. J.和Fan，Y.1996。统计软件包中的样本分位数，American Statistician 50，361–365。 https://doi.org/10.2307/2684934