Programma Lezione 136 di 148 · Batti il tuo Fantasma
Batti il tuo Fantasma

Niente ordinamento: il rapporto sulla latenza

Perché è importante "Prima ordinalo" trasforma molti problemi in problemi facili, quindi diventa automatico. Alcuni dati hanno una forma per cui ordinare è la strada lunga.

Un servizio registra quanto ha impiegato ogni richiesta, in millisecondi interi. Le richieste vanno in timeout a 10 secondi, quindi ogni valore è tra 0 e 10,000. Ogni minuto, un lavoro trasforma circa 20,000 valori nei numeri della dashboard di reperibilità: la mediana, il 90° e il 99° percentile, e il peggiore.

Percentile per rango più vicino: il p-esimo percentile è il valore più piccolo tale che almeno il p% di tutti i valori sia uguale o inferiore. Con 20 valori, il 90° percentile è il 18° più piccolo.

I dati

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

In questo problema ordinare è vietato, a mano o con una libreria. Guarda che cosa sai dei valori.

Tocca a te

Scrivi latency_report(values). values è una lista non vuota di numeri interi da 0 a 10,000 (circa 20,000). Restituisci {"p50", "p90", "p99", "max"}: il 50°, il 90° e il 99° percentile per rango più vicino (il valore più piccolo con almeno il p% dei valori uguale o inferiore) e il valore più grande. Non modificare la lista. Regola: niente ordinamento: niente sorted(), .sort(), bisect.insort, e niente import di heapq o statistics (ordinano al posto tuo).

Hai notato un problema in questa lezione? Segnalalo · Chiedi qualcosa su questa lezione

Questo esercizio si apre presto

Finisci la lezione precedente e questa si sblocca. L'intero corso è gratuito, senza account, e puoi leggere questa lezione subito.