Lehrplan Lektion 54 von 148 · Geschwindigkeit ohne den Cache
Geschwindigkeit ohne den Cache

Einmal vorberechnen

Warum das wichtig ist "Gesamtwert von X zwischen zwei Punkten" ist eine der häufigsten Fragen in Reporting-Code. Jede einzelne durch das Aufsummieren des Bereichs zu beantworten ist langsam; einen Gesamtwert für jeden Punkt zu behalten kann zu groß sein. Es gibt einen Weg dazwischen.

A shop behält 60.000 Tage an Verkäufen in einem metered store, der dir als Tape übergeben wird. Finance sendet eine Charge von 50 Fragen auf einmal: "Gesamtverkäufe von Tag a bis Tag b". Du läufst auf einem kleinen worker mit sehr wenig freiem Speicher.

Laufendes Gesamtergebnis (Präfixsumme): die Summe von allem vor einer Position. Das Gesamtergebnis eines Fensters ist das laufende Gesamtergebnis am Ende minus das laufende Gesamtergebnis am Anfang.

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

Schreibe range_totals(tape, queries). tape ist ein Tape der täglichen Verkäufe (Ganzzahlen). queries ist eine Liste von (start, end) Paaren mit 0 <= start <= end <= len(tape). Gib eine Liste mit der Summe von tape[start:end] für jede Abfrage zurück, in der gegebenen Reihenfolge. Budgets: lies das Tape höchstens einmal (60,100 Lesevorgänge für 60,000 Tage und 50 Abfragen) und verwende höchstens 100,000 Bytes Arbeitsspeicher, während deine Funktion läuft (gemessen mit tracemalloc; eine laufende Summe für jeden Tag oder sogar eine einfache Liste der 60,000 Werte liegt weit über 100,000 Bytes). Alle Fragen kommen zusammen an, bevor du die Daten liest.

Ein Problem in dieser Lektion entdeckt? Melde es · Frage zu dieser Lektion

Diese Übung öffnet bald

Beende die vorherige Lektion, damit diese freigeschaltet wird. Der ganze Kurs ist kostenlos, kein Konto erforderlich, und du kannst diese Lektion jetzt direkt lesen.