Eenmalig vooraf berekenen
Waarom dit ertoe doet "Totaal van X tussen twee punten" is een van de meest voorkomende vragen in reporting code. Elke vraag beantwoorden door de range op te tellen is traag; een totaal bijhouden voor elk punt kan te groot zijn. Er is een route tussen de twee.
A winkel houdt 60.000 dagen aan verkopen bijhouden in een metered store, die aan je wordt gegeven als een Tape. Finance stuurt een batch van 50 vragen tegelijk: "totale verkopen van dag a tot dag b". Je draait op een kleine worker met heel weinig vrij geheugen.
Lopend totaal (prefix sum): de som van alles voor een positie. Het totaal van een window is het lopend totaal aan het einde minus het lopend totaal aan het begin.
sales = [5, 1, 4, 2, 8]
# running totals before each position: 0, 5, 6, 10, 12, 20
# window (1, 4) = 12 - 5 = 7Schrijf range_totals(tape, queries). tape is een Tape van dagelijkse verkopen (gehele getallen). queries is een lijst van (start, end) paren met 0 <= start <= end <= len(tape). Geef een lijst terug met de totaal van tape[start:end] voor elke query, in de gegeven volgorde. Budgets: lees de tape maximaal één keer (60,100 reads voor 60,000 dagen en 50 queries), en gebruik maximaal 100,000 bytes aan werkgeheugen terwijl je functie draait (gemeten met tracemalloc; een lopend totaal voor elke dag, of zelfs een simpele lijst van de 60,000 waarden, is ruim boven de 100,000 bytes). De vragen komen allemaal tegelijk aan, voordat je de data leest.
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.
Deze browser blokkeert cookies voor learn.floati.life, dus lessen die je hier hebt afgerond kunnen niet in de juiste volgorde worden geopend. Sta cookies toe voor deze site en laad de pagina opnieuw.