1

1 日に何百万ものリクエストを受信する rpc サーバーが提供されます。各リクエスト i が処理されるまでに処理時間 Ti がかかります。任意の時点での 65 パーセンタイルの処理時間 (処理時間が値の昇順で並べ替えられている場合) を見つけたいと考えています。リクエスト数が非常に多いため、過去のすべてのリクエストの処理時間を保存することはできません。そのため、答えは正確な 65 パーセンタイルである必要はありません。正確な 65 パーセンタイル数に近い処理時間など、おおよその答えを出すことができます。

ヒント: すべてのデータを保存するのではなく、非常に大きなデータのヒストグラム (つまり、概要) を保存する方法です。

4

4 に答える 4

2

1 日分のデータを取得します。それを使用して、バケットを作成するサイズを決定します (ある日のデータで、データの大部分 (95%?) が 1 秒の 0.5 秒以内にあることが示されているとします (ばかげた値ですが、我慢してください))。

65 パーセンタイルを取得するには、その範囲内に少なくとも 20 個のバケットが必要ですが、余裕を持って 80 個にします。したがって、1 秒のウィンドウ (-0.5 秒から +0.5 秒) を 80 個のバケットに分割します。 80 分の 1 秒の幅。

各バケットは 1 秒の 1/80 です。バケット 0 を (中心 - 偏差) = (1 - 0.5) = 0.5 からそれ自体 + 1/80 秒にします。バケット 1 は 0.5+1/80 - 0.5 + 2/80 です。等。

すべての値について、どのバケットに該当するかを調べ、そのバケットのカウンターをインクリメントします。

65 パーセンタイルを見つけるには、合計数を取得し、その合計の 65% になるまでバケットをゼロから調べます。

リセットしたいときはいつでも、カウンターをすべてゼロに設定してください。

常に適切なデータを利用できるようにしたい場合は、これらのうちの 2 つを保持し、より有用なデータがあるとして最も最近リセットしたものを使用して、交互にリセットします。

于 2010-06-21T00:38:24.913 に答える
1

アップダウン フィルターを使用します。

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 パーセンタイルで浮き上がります。一般に、up / (up + down) パーセンタイルを追跡します。アップ/ダウン ファクターが大きいほど、追跡は速くなりますがノイズが多くなります。実際のデータで実験する必要があります。

（アップダウンを分析する方法がわかりません。リンクをいただければ幸いです。）

以下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()
于 2010-07-01T09:11:26.090 に答える
0

リストまたは配列の特定のパーセンタイルを表す値を取得する簡単な方法は、scipy.stats モジュールの scoreatpercentile 関数です。

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

指定された値のパーセンタイルを返す兄弟のパーセンタイル オブ スコアがあります。

于 2010-10-07T02:42:01.207 に答える
-1

実行中の合計と合計数を保存する必要があります。

次に、標準偏差の計算を確認してください。

于 2010-06-21T00:21:39.480 に答える