Programme Leçon 136 sur 148 · Bats ton Fantôme
Bats ton Fantôme

Pas de tri : le rapport de latence

Pourquoi c'est important « Trie d'abord » rend beaucoup de problèmes faciles, donc ça devient automatique. Certaines données ont une forme qui fait du tri le chemin le plus long.

Un service enregistre la durée de chaque requête, en millisecondes entières. Les requêtes expirent à 10 secondes, donc chaque valeur est entre 0 et 10 000. Chaque minute, une tâche transforme environ 20 000 valeurs en chiffres pour le tableau de bord d'astreinte : la médiane, les 90e et 99e centiles, et le pire.

Centile au rang le plus proche : le p-ième centile est la plus petite valeur telle qu'au moins p % de toutes les valeurs lui soient inférieures ou égales. Avec 20 valeurs, le 90e centile est la 18e plus petite.

Les données

values = [120, 85, 3000, 95, 110, 90, 100, 105, 80, 130]
# latency_report(values) -> {"p50": 100, "p90": 130, "p99": 3000, "max": 3000}

Dans ce problème, le tri est interdit, à la main ou par une bibliothèque. Regarde ce que tu sais des valeurs.

À ton tour

Écris latency_report(values). values est une liste non vide de nombres entiers de 0 à 10 000 (environ 20 000). Renvoie {"p50", "p90", "p99", "max"} : les 50e, 90e et 99e centiles au rang le plus proche (la plus petite valeur avec au moins p % des valeurs inférieures ou égales) et la plus grande valeur. Ne modifie pas la liste. Règle : pas de tri : pas de sorted(), .sort(), bisect.insort, et pas d'import de heapq ou statistics (ils trient pour toi).

Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon

Cet exercice s'ouvre bientôt

Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.