Nearest rank ile gecikme yüzdelikleri
Görev tanımı
Problem
Bir dashboard istek gecikmesini (latency) bir ortalama yerine yüzdelikler olarak raporluyor. Milisaniye cinsinden gecikme örneklerinden oluşan bir liste ve [50, 90, 99] gibi bir yüzdelik listesi verildiğinde, nearest-rank yöntemiyle her yüzdelikten değerine giden bir dict döndür: örnekleri sırala; p. yüzdelik, n örnek sayısı olmak üzere 1 tabanlı ceil(p × n / 100) sırasındaki örnektir. Sıra için tam sayı aritmetiği kullan. En fazla 1.000.000 örnek var.
Örnekler
Input: latencies = [12, 15, 11, 13, 240, 14, 12, 16, 13, 12], ps = [50, 90, 99]
Output: {50: 13, 90: 16, 99: 240}
Neden: ondaki bir yavaş istek p90'da görünmez, p99'da ise bütün hikâyedir
Input: latencies = 1 to 100, ps = [50, 90, 99, 100]
Output: {50: 50, 90: 90, 99: 99, 100: 100}
Neden: 100 örnekle p. yüzdelik basitçe p. en küçüktür
Input: latencies = [7], ps = [50, 99]
Output: {50: 7, 99: 7}
Neden: edge case: tek bir örnek her yüzdeliktir
İpuçları
0 / 3
Bir yüzdelik sıralı düzende bir konumdur; yani bir kez sırala, her yüzdelik bir aramaya dönüşsün.
Sıra ceil(p × n / 100)'dür. Tam sayılarda bu (p × n + 99) // 100'dür; bu da 0.29 × 100'ün tam olarak 29 olmaması gibi kayan nokta sürprizlerinden kaçınır.
Sıralar 1 tabanlı, liste 0 tabanlı; yani sıra - 1 indeksini oku. Küçük bir listede çok küçük bir yüzdelik yine en küçük örneği döndürsün diye sırayı en az 1'e sabitle.
- Hedef zaman
- O(n log n + q)
- Hedef alan
- O(n)
Kısıtlar
- at most 10⁶ samples
Çözüm
Ortalamalar kullanıcıların gerçekten hissettiği yavaş uçtaki istekleri, yani tail latency'yi gizler; dashboard'ların p50, p90 ve p99'u izlemesinin sebebi bu, ilk örnek de bunu gösterir: o on örneğin ortalaması yaklaşık 36 ms'dir, hiçbir isteğin yaklaşmadığı bir sayı. Nearest rank, her zaman gerçek bir örnek döndüren en basit yüzdelik tanımıdır: sırala, ceil(p × n / 100) sırasını tam sayı aritmetiğiyle hesapla ve o konumu oku. Sırayı 1'de sabitlemek çok küçük yüzdelikleri kısa listelerde geçerli tutar. Sıralama baskındır; q yüzdelik için zaman O(n log n + q), sıralı kopya için alan O(n).
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}Kodda değil de fikirde mi takıldın? Gözlemlenebilirliğin temelleri bunu anlatıyor.