2010-06-21 3 views
1

Получается сервер rpc, который получает миллионы запросов в день. Каждый запрос i обрабатывает время обработки Ti для обработки. Мы хотим найти время обработки 65-го процентиля (когда время обработки сортируется в соответствии с их значениями в порядке возрастания) в любой момент. Мы не можем хранить время обработки всех запросов прошлого, так как количество запросов очень велико. И поэтому ответ не обязательно должен быть точным 65-м процентилем, вы можете дать приблизительный ответ, то есть время обработки, которое будет составлять около 65-го процентиля.Нужна помощь при вычислении процентиля

Подсказка: что-то делать, когда гистограмма (т. Е. Обзор) хранится для очень больших данных без сохранения всех данных.

ответ

1

Возьмите данные за один день. Используйте его, чтобы выяснить, какой размер сделать ваши ведра (скажем, данные за один день показывают, что подавляющее большинство (95%?) Ваших данных находится в пределах 0,5 секунды до 1 секунды (смешные значения, но зависание)

Чтобы получить 65-го процентиля, вам понадобится не менее 20 ведер в этом диапазоне, но будьте щедрыми и сделайте это 80. Таким образом, вы разделите свое 1-секундное окно (от -0,5 секунды до +0,5 секунд) на 80 ковшей, сделав каждый 1/80 второй шириной

Каждый ковш равен 1/80 секунды 1 секунда. Сделать ведро 0 (центральное отклонение) = (1 - 0,5) = 0,5 для себя + 1/80 часть секунды. Ковш 1 равен 0,5+ 1/80-й - 0,5 + 2/80-е годы. И т.д.

Для каждого значения выясните, в каком ковше оно входит, и увеличьте счетчик для этого ведра.

Чтобы найти 65-й процентиль, получите общее количество и проведите ведра с нуля, пока не получите 65% от этой суммы.

Всякий раз, когда вы хотите сбросить, установите все счетчики равными нулю.

Если вы всегда хотите иметь хорошие данные, сохраните два из них и поочередно переустановите их, используя тот, который вы сбросили в последнее время как имеющее более полезные данные.

-1

вам нужно будет сохранить текущую сумму и общее количество.

затем проверьте стандартные отклонения.

+0

-1 на самом деле? я делаю именно это - и он работает как шарм ... – Randy

+0

Этот подход будет работать, только если данные обычно (т. е. гауссовские) распределены. – eglaser

1

Используйте 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-й процентиль. С .01 вверх, .005 вниз, он плавает вверх, 67-й процентиль; в целом, он отслеживает вверх/(вверх + вниз) th процентили. Большие факторы вверх/вниз отслеживают быстрее, но шумнее - вам придется экспериментировать с вашими реальными данными.

(я понятия не имею, как анализировать updowns, был бы признателен за ссылку.)

updown() ниже работает на длинных векторов X, Q, чтобы построить их: alt text

#!/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() 
+1

Похоже, что updown отслеживает некоторый предвзятый вариант среднего, а не медиана. –

+0

На самом деле это была бы хорошая оценка среднего значения, если $ q_ {n} + = (x_ {n} - q_ {n-1})/n $ – Wok

+0

@wok, попробуйте разные коэффициенты вверх/вниз – denis

0

более простой способ получить значение, представляющее данный процентиль списка или массива, - это функция scoretpercentile в scipy.статистика.

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

есть брат percentileofscore вернуть процентиль заданного значения

Смежные вопросы