Kurrikulum Leson 54 van 148 · Spoed sonder die cache
Spoed sonder die cache

Bereken vooraf een keer

Waarom dit saak maak "Totaal van X tussen twee punte" is een van die algemeenste vrae in rapporteringskode. Om elk een deur die reeks bymekaar te tel is stadig; om 'n totaal vir elke punt te hou kan te groot wees. Daar is 'n roete tussen die twee.

A winkel hou 60,000 dae se verkope op 'n metered store, wat aan jou gegee word as 'n Tape. Finansie stuur 'n pakkie van 50 vrae gelyktydig: "totale verkope vanaf dag a tot dag b". Jy hardloop op 'n klein worker met baie min vrye geheue.

Lopende totaal (prefix sum): die som van alles voor 'n posisie. Die totaal van 'n venster is die lopende totaal by die einde minus die lopende totaal by die begin.

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

Skryf range_totals(tape, queries). tape is 'n Tape van daaglikse verkope (heeltallige getalle). queries is 'n lys van (start, end)-paaie met 0 <= start <= end <= len(tape). Gee 'n lys met die totaal van tape[start:end] vir elke navraag, in die volgorde wat gegee word. Budgets: lees die band hoogstens een keer (60,100 leesies vir 60,000 dae en 50 navrae), en gebruik hoogstens 100,000 bytes van werksgeheue terwyl jou funksie loop (gemeet met tracemalloc; 'n lopende totaal vir elke dag, of selfs 'n eenvoudige lys van die 60,000 waardes, is ver bo 100,000 bytes). Die vrae kom almal gelyk saam aan, voordat jy die data lees.

Sien jy 'n probleem in hierdie les? Rapporteer dit · Vra oor hierdie les

Hierdie oefening open binnekort

Voltooi die lesie voor dit en hierdie een sal ontvanklik wees. Die hele kursus is gratis, geen rekening nodig nie, en jy kan hierdie les nou lees.