c - 需要一些帮助来计算百分位数

Question

给出了一个 rpc 服务器，它每天接收数百万个请求。每个请求 i 需要处理时间 Ti 才能得到处理。我们想在任何时候找到第 65 个百分位的处理时间（当处理时间根据它们的值按升序排序时）。我们无法存储过去所有请求的处理时间，因为请求的数量非常大。所以答案不必是精确的第 65 个百分位，您可以给出一些近似的答案，即处理时间大约是精确的第 65 个百分位数字。

提示：它与如何在不存储所有数据的情况下为非常大的数据存储直方图（即概览）有关。

Answer 1

取一天的数据。用它来确定你的桶的大小（比如一天的数据显示绝大多数（95%？）你的数据在 1 秒的 0.5 秒内（荒谬的值，但坚持下去）

要获得第 65 个百分位数，您需要在该范围内至少有 20 个桶，但要大方，将其设为 80。因此，您将 1 秒窗口（-0.5 秒到 +0.5 秒）分成 80 个桶，每个 1/ 80 秒宽。

每个桶是 1 秒的 1/80。使桶 0 为 (中心 - 偏差) = (1 - 0.5) = 0.5 到自身 + 1/80 秒。桶 1 是 0.5+1/80th - 0.5 + 2/80ths。等等。

对于每个值，找出它属于哪个桶，并为该桶增加一个计数器。

要找到第 65 个百分位数，请获取总数，然后从零开始遍历存储桶，直到达到总数的 65%。

每当您想重置时，请将计数器全部设置为零。

如果您总是希望有好的数据可用，请保留其中两个，并交替重置它们，使用您最近最少重置的一个作为拥有更多有用数据的数据。

Answer 2

使用 updown 过滤器：

if q < x:
    q += .01 * (x - q)  # up a little
else:
    q += .005 * (x - q)  # down a little

这里分位数估计器q跟踪x流，向每个 移动一点x。如果这两个因素都是 0.01，它会上升和下降一样频繁，跟踪第 50 个百分位。随着 0.01 向上，0.005 向下，它向上浮动，第 67 个百分位；一般来说，它跟踪上/（上+下）个百分位数。较大的向上/向下因子跟踪速度更快但噪音更大——您必须对真实数据进行试验。

（我不知道如何分析起伏，希望有一个链接。）

以下updown()适用于长向量 X、Q 以绘制它们：

#!/usr/bin/env python
from __future__ import division
import sys
import numpy as np
import pylab as pl

def updown( X, Q, up=.01, down=.01 ):
    """ updown filter: running ~ up / (up + down) th percentile
        here vecs X in, Q out to plot
    """
    q = X[0]
    for j, x in np.ndenumerate(X):
        if q < x:
            q += up * (x - q)  # up a little
        else:
            q += down * (x - q)  # down a little
        Q[j] = q
    return q

#...............................................................................
if __name__ == "__main__":

    N = 1000
    up = .01
    down = .005
    plot = 0
    seed = 1
    exec "\n".join( sys.argv[1:] )  # python this.py N= up= down=
    np.random.seed(seed)
    np.set_printoptions( 2, threshold=100, suppress=True )  # .2f

    title = "updown random.exponential: N %d  up %.2g  down %.2g" % (N, up, down)
    print title
    X = np.random.exponential( size=N )
    Q = np.zeros(N)
    updown( X, Q, up=up, down=down )
        # M = np.zeros(N)
        # updown( X, M, up=up, down=up )
    print "last 10 Q:", Q[-10:]
    if plot:
        fig = pl.figure( figsize=(8,3) )
        pl.title(title)
        x = np.arange(N)
        pl.plot( x, X, "," )
        pl.plot( x, Q )
        pl.ylim( 0, 2 )
        png = "updown.png"
        print >>sys.stderr, "writing", png
        pl.savefig( png )
        pl.show()

Answer 3

获取表示列表或数组的给定百分位数的值的更简单方法是 scipy.stats 模块中的 scoreatpercentile 函数。

>>>import scipy.stats as ss
>>>ss.scoreatpercentile(v,65)

有一个兄弟 percentileofscore 返回给定值的百分位数

Answer 4

您将需要存储运行总和和总计数。

然后检查标准偏差计算。