Programma Lezione 54 di 148 · Velocità senza cache
Velocità senza cache

Precalcola una volta

Perché è importante "Totale di X tra due punti" è una delle domande più comuni nel codice di reportistica. Rispondere a ciascuna sommando l'intervallo è lento; tenere un totale per ogni punto può essere troppo grande. C'è una strada tra le due.

Un negozio tiene 60,000 giorni di vendite su un archivio a consumo, che ti viene dato come Tape. La finanza manda un gruppo di 50 domande insieme: "vendite totali dal giorno a fino al giorno b". Giri su un piccolo worker con pochissima memoria libera.

Totale progressivo (somma prefissa): la somma di tutto ciò che sta prima di una posizione. Il totale di una finestra è il totale progressivo alla sua fine meno il totale progressivo al suo inizio.

sales = [5, 1, 4, 2, 8]
# running totals before each position: 0, 5, 6, 10, 12, 20
# window (1, 4) = 12 - 5 = 7
Tocca a te

Scrivi range_totals(tape, queries). tape è un Tape di vendite giornaliere (numeri interi). queries è una lista di coppie (start, end) con 0 <= start <= end <= len(tape). Restituisci una lista con il totale di tape[start:end] per ogni domanda, nell'ordine dato. Budget: leggi il tape al massimo una volta (60,100 letture per 60,000 giorni e 50 domande), e usa al massimo 100,000 byte di memoria di lavoro mentre la tua funzione gira (misurati con tracemalloc; un totale progressivo per ogni giorno, o anche una semplice lista dei 60,000 valori, supera di molto i 100,000 byte). Le domande arrivano tutte insieme, prima che tu legga i dati.

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.