Besoin d'aide pour calculer le percentile

Question

Un serveur rpc est fourni qui reçoit des millions de demandes par jour. Chaque requête i prend le temps de traitement Ti pour être traitée. Nous voulons trouver le temps de traitement du 65ème centile (lorsque les temps de traitement sont triés en fonction de leurs valeurs dans l'ordre croissant) à tout moment. Nous ne pouvons pas stocker les temps de traitement de toutes les requêtes du passé car le nombre de requêtes est très important. Et donc la réponse ne doit pas être exacte au 65ème centile, vous pouvez donner une réponse approximative, c'est-à-dire le temps de traitement qui sera autour du nombre exact du 65ème centile. Astuce: C'est quelque chose à faire comment un histogramme (c'est-à-dire une vue d'ensemble) est stocké pour une très grande quantité de données sans stocker toutes les données.

Answer 1

Prendre les données d'une journée. Utilisez-le pour déterminer la taille de vos seaux (par exemple, les données d'un jour montrent que la grande majorité (95%?) De vos données est à 0,5 secondes de 1 seconde (valeurs ridicules, mais pendantes)

Pour obtenir 65e percentile, vous aurez besoin d'au moins 20 seaux dans cette gamme, mais soyez généreux, et faites-en 80. Donc, vous divisez votre 1 seconde fenêtre (-0,5 secondes à +0,5 secondes) en 80 seaux en faisant chaque 1/80e de

Chaque godet mesure 1/80ème de seconde, le godet 0 étant (écart au centre) = (1 - 0.5) = 0.5 à lui-même + 1/80ème de seconde. 1/80th - 0.5 + 2/80ths Etc.

Pour chaque valeur, trouvez dans quel godet il se trouve, et incrémenter un compteur pour ce compartiment.

Pour trouver le 65e centile, obtenez le nombre total et faites passer les godets de zéro jusqu'à ce que vous atteigniez 65% de ce total. Chaque fois que vous voulez réinitialiser, réglez tous les compteurs à zéro.

Si vous souhaitez toujours disposer de bonnes données, conservez-en deux et remplacez-les par d'autres, en utilisant celui que vous avez réinitialisé le moins récemment comme ayant des données plus utiles.

Answer 2

vous aurez besoin de stocker une somme courante et un nombre total.

puis de vérifier les calculs d'écart-type.

Answer 3

Utilisez un filtre updown:

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

Voici un estimateur quantile q suit le flux x, déplacer un peu vers chaque x. Si les deux facteurs étaient 0,01, il monterait aussi souvent que vers le bas, en suivant le 50 e centile. Avec 0,01 vers le haut, 0,005 vers le bas, il flotte, 67 e centile; en général, il suit l'up/(up + down) percentile th. Plus les facteurs montés/descendus sont rapides, mais plus bruyants - vous devrez expérimenter sur vos données réelles.

(Je ne sais pas comment analyser updowns, apprécierait un lien.)

Le updown() fonctionne ci-dessous sur les longs vecteurs X, Q afin de les tracer:

#!/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 4

Une La fonction scoreatpercentile dans scipy est la façon la plus simple d'obtenir la valeur qui représente un centile donné d'une liste ou d'un tableau.module stats.

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

il y a un frère percentileofscore pour ramener le percentile compte tenu de la valeur