Percentiles de latencia por nearest rank
La misión
Problema
Un panel informa la latencia de las solicitudes como percentiles en lugar de un promedio. Dada una lista de muestras de latencia en milisegundos y una lista de percentiles como [50, 90, 99], devuelve un dict de cada percentil a su valor usando el método del rango más cercano (nearest rank): ordena las muestras, y el percentil p es la muestra en el rango ceil(p × n / 100), contado desde 1, donde n es la cantidad de muestras. Usa aritmética entera para el rango. Hay hasta un millón de muestras.
Ejemplos
Input: latencies = [12, 15, 11, 13, 240, 14, 12, 16, 13, 12], ps = [50, 90, 99]
Output: {50: 13, 90: 16, 99: 240}
Por qué: una solicitud lenta de cada diez es invisible en p90 y lo es todo en p99
Input: latencies = 1 to 100, ps = [50, 90, 99, 100]
Output: {50: 50, 90: 90, 99: 99, 100: 100}
Por qué: con 100 muestras, el percentil p es simplemente el p-ésimo valor más pequeño
Input: latencies = [7], ps = [50, 99]
Output: {50: 7, 99: 7}
Por qué: caso límite: una sola muestra es todos los percentiles
Pistas
0 / 3
Un percentil es una posición dentro de los datos ordenados, así que ordena una vez y cada percentil se vuelve una consulta directa.
El rango es ceil(p × n / 100). En enteros, eso es (p × n + 99) // 100, lo que evita sorpresas del punto flotante, como que 0.29 × 100 no dé exactamente 29.
Los rangos empiezan en 1 y la lista empieza en 0, así que lee el índice rango - 1. Limita el rango a un mínimo de 1 para que un percentil muy pequeño en una lista corta siga devolviendo la muestra más pequeña.
- Tiempo objetivo
- O(n log n + q)
- Espacio objetivo
- O(n)
Restricciones
- at most 10⁶ samples
Solución
Los promedios ocultan la cola lenta que los usuarios realmente sienten, y por eso los paneles siguen p50, p90 y p99; el primer ejemplo lo muestra: el promedio de esas diez muestras es de unos 36 ms, un número al que ninguna solicitud se acercó. El rango más cercano es la definición de percentil más simple que siempre devuelve una muestra real: ordenar, calcular el rango ceil(p × n / 100) con aritmética entera y leer esa posición. Limitar el rango a un mínimo de 1 mantiene válidos los percentiles muy pequeños en listas cortas. El ordenamiento (sorting) domina, así que el tiempo es O(n log n + q) para q percentiles, y el espacio es O(n) para la copia ordenada.
def percentiles(latencies, ps):
ranked = sorted(latencies)
n = len(ranked)
return {p: ranked[max(1, (p * n + 99) // 100) - 1] for p in ps} # ceil(p * n / 100), 1-based
print(percentiles([12, 15, 11, 13, 240, 14, 12, 16, 13, 12], [50, 90, 99])) # -> {50: 13, 90: 16, 99: 240}
print(percentiles(list(range(1, 101)), [50, 90, 99, 100])) # -> {50: 50, 90: 90, 99: 99, 100: 100}
print(percentiles([7], [50, 99])) # -> {50: 7, 99: 7}¿Lo que te frena es la idea y no el código? Fundamentos de observabilidad lo explica.