Programma Les 136 van 148 · Breek je eigen record
Breek je eigen record

Geen sortering: het latency rapport

Waarom dit ertoe doet "Sorteer het eerst" maakt veel problemen makkelijk, zodat het automatisch wordt. Sommige data is zo gevormd dat sorteren de lange weg is.

A service houdt bij hoe lang elke request duurde, in hele milliseconden. Requests time out na 10 seconden, dus elke waarde ligt tussen 0 en 10,000. Elke minuut zet een job ongeveer 20,000 waarden om naar de getallen op het on-call dashboard: de median, de 90e en 99e percentielen, en de slechtste.

Nearest-rank percentile: het p-ste percentiel is de kleinste waarde waarbij ten minste p% van alle waarden er op of onder liggen. Met 20 waarden is het 90ste percentiel de 18ste kleinste.

De data

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

In dit probleem is sorteren verboden, met de hand of via een library. Kijk naar wat je weet over de waarden.

Jij bent aan de beurt

Schrijf latency_report(values). values is een niet-lege lijst van gehele getallen van 0 tot 10,000 (ongeveer 20,000 van hen). Geef {"p50", "p90", "p99", "max"} terug: de nearest-rank 50e, 90e en 99e percentielen (de kleinste waarde met ten minste p% van de waarden op of onder deze waarde) en de grootste waarde. Verander de lijst niet. Regel: geen sorteren: geen sorted(), .sort(), bisect.insort, en geen heapq of statistics imports (die sorteren voor je).

Een probleem ontdekt in deze les? Meld het · Vraag naar deze les

Deze oefening opent binnenkort

Maak de les ervoor af voordat deze wordt ontgrendeld. De hele cursus is gratis, geen account nodig, en je kunt deze les nu lezen.