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

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/80th。等。

对于每个值，找出它所在的存储桶，并为该存储桶增加一个计数器。

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

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

如果您希望始终有良好的数据可用，请保留其中的两个，并交替重置它们，使用您最近重置最少的一个，因为它具有更有用的数据。

Answer 2

使用向上向下过滤器：

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

在这里，分位数估计器q跟踪x流，向每个x移动一点。如果这两个因素都是.01，它将向上和向下移动，跟踪第50个百分位数。使用.01 up，.005 down，它向上浮动，第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)

对于给定的值，有一个同级百分比there来返回百分位数