Percentis de latência por nearest rank
A missão
Problema
Um painel mostra a latência das requisições como percentis, e não como média. Dadas uma lista de amostras de latência em milissegundos e uma lista de percentis, como [50, 90, 99], retorne um dicionário de cada percentil para o seu valor usando o método nearest rank (posto mais próximo): ordene as amostras, e o p-ésimo percentil é a amostra na posição ceil(p × n / 100), indexada a partir de 1, em que n é o número de amostras. Use aritmética inteira para a posição. Há até 1.000.000 de amostras.
Exemplos
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ê: uma requisição lenta em dez é invisível no p90 e é a história toda no p99
Input: latencies = 1 to 100, ps = [50, 90, 99, 100]
Output: {50: 50, 90: 90, 99: 99, 100: 100}
Por quê: com 100 amostras, o p-ésimo percentil é simplesmente o p-ésimo menor valor
Input: latencies = [7], ps = [50, 99]
Output: {50: 7, 99: 7}
Por quê: edge case: uma única amostra é todos os percentis
Dicas
0 / 3
Um percentil é uma posição na lista ordenada, então ordene uma vez e cada percentil vira uma simples leitura.
A posição é ceil(p × n / 100). Em inteiros, isso é (p × n + 99) // 100, o que evita surpresas de ponto flutuante, como 0,29 × 100 não dar exatamente 29.
As posições são indexadas a partir de 1 e a lista, a partir de 0, então leia o índice rank - 1. Garanta que a posição seja pelo menos 1, para que um percentil minúsculo em uma lista pequena ainda retorne a menor amostra.
- Tempo-alvo
- O(n log n + q)
- Espaço-alvo
- O(n)
Restrições
- at most 10⁶ samples
Solução
As médias escondem a cauda lenta que os usuários de fato sentem, e é por isso que os painéis acompanham p50, p90 e p99; o primeiro exemplo mostra isso: a média daquelas dez amostras é cerca de 36 ms, um número de que nenhuma requisição chegou perto. O nearest rank é a definição de percentil mais simples que sempre retorna uma amostra real: ordene, calcule a posição ceil(p × n / 100) com aritmética inteira e leia essa posição. Garantir que a posição seja pelo menos 1 mantém válidos os percentis muito pequenos em listas curtas. A ordenação domina, então o tempo é O(n log n + q) para q percentis, e o espaço é O(n) para a cópia 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}Travou na ideia, e não no código? O básico de observabilidade explica isso.