Нужна некоторая вычислительная процентиль справки
rpc сервер дан, который получает миллионы запросов в день. Каждый запрос i занимает время обработки Ti, который будет обработан. Мы хотим найти 65-е время обработки процентили (когда время обработки отсортировано согласно их значениям в увеличивающемся порядке), в любой момент. Мы не можем сохранить время обработки всех запросов прошлого, поскольку количество запросов является очень большим. И таким образом, ответ не должен быть точной 65-й процентилью, можно дать некоторый приблизительный ответ т.е. время обработки, которое будет вокруг точного 65-го числа процентили.
Подсказка: что-то, чтобы сделать, как гистограмма (т.е. обзор) хранится для очень больших данных, не храня все данные.
3 ответа
Возьмите данные за один день. Используйте его, чтобы выяснить, какого размера делать ведра (скажем, данные одного дня показывают, что подавляющее большинство (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/80th - 0,5 + 2/80th. И т.д.
Для каждого значения выясните, в какое ведро оно попадает, и увеличьте счетчик для этого ведра.
Чтобы найти 65-й процентиль, возьмите общий счетчик и пройдитесь по ведрам от нуля, пока не дойдете до 65% от этого общего числа.
Всякий раз, когда вы хотите сбросить данные, установите все счетчики на ноль.
Если вы хотите всегда иметь в наличии хорошие данные, держите два таких счетчика и попеременно сбрасывайте их, используя тот, который вы сбросили меньше всего, как имеющий больше полезных данных.
вам нужно будет хранить текущую сумму и общий счет.
затем проверьте вычисления стандартного отклонения.
Используйте восходящий фильтр:
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,05 вниз он всплывает вверх, 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()