Lehrplan Lektion 77 von 148 · Ungerade Grenzen
Ungerade Grenzen

Fester Speicher

Warum das wichtig ist "Zähle, wie oft jede Sache passiert" ist ein Dictionary, bis die Anzahl der Sachen unbegrenzt ist und der Speicher nicht. Eine ungefähre Zählung mit einer garantierten Grenze ist oft viel mehr wert als eine exakte Zählung, die du dir nicht leisten kannst.

Ein API gateway markiert starke Nutzer. Es sieht jeden request, es kann jede Anzahl an Nutzern geben, und jeder gateway process erhält einen festen Anteil an Speicher für diese Aufgabe. Die Markierung ist nur ein Hinweis für einen Menschen zum Nachsehen, also ist eine kleine Überzählung in Ordnung; eine Unterzählung könnte einen starken Nutzer verbergen, also ist sie nicht.

Sketch: eine Zusammenfassung fester Größe eines Streams, die Fragen näherungsweise beantwortet, mit einer bekannten Fehlergrenze. Ein count-min sketch behält zum Beispiel einige Zeilen von Zählern und hasht jedes Element auf einen Zähler pro Zeile; der kleinste dieser Zähler liegt niemals unter dem wahren Zählerstand.

import zlib
row_index = zlib.crc32(f"{row}:{item}".encode()) % width   # same on every run
Du bist dran

Schreibe class ApproxCounter mit add(item) (Elemente sind Strings) und estimate(item) (eine ganze Zahl).

Limits. Nach 30.000 Ereignissen von bis zu 10.000 verschiedenen Nutzern kann der Zähler höchstens 3.500 Elemente halten (kept() auf dem Zähler). Schätzungen dürfen niemals unter der wahren Anzahl liegen, und für mindestens 95% der Nutzer (einschließlich Nutzer, die nie gesehen wurden) müssen sie höchstens die wahre Anzahl plus 300 (1% der Ereignisse) betragen. Ergebnisse müssen bei jedem Durchlauf und auf jedem Gerät wiederholbar sein: verwende nicht hash() (es ändert sich pro Durchlauf) oder Zufallszahlen; zlib.crc32 oder hashlib mit festen Seeds sind in Ordnung.

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.