Datenstrukturdienstag:
Letzte Woche: Zählen, wie oft bestimmte Elemente vorkamen.
Diese Woche: Zählen, wie viele Elemente in einer Menge enthalten sind.

Verwenden kann man dafür HyperLogLog (ja, wieder probabilistisch).

Anwendungsfall: Ihr habt eine Menge, zu der ständig neue Elemente hinzukommen. Ihr braucht euch nicht jedes Element merken. Aber es kann sein, dass ein Element, das eigentlich schon drin ist, noch mal hinzugefügt werden soll. Ihr wollt dieses Element nicht doppelt zählen (Fachbegriff Count-Distinct-Problem).

Konkret wollt ihr vielleicht die Anzahl der Aufrufe eines Videos zählen und nimmt dabei die ID des Users, der es angesehen hat, als Kriterium. Schaut sich die Person es noch mal an, wollt ihr sie nicht noch mal zählen. HLL hat dabei einen sehr langsam wachsenden Speicherbedarf (ursprünglich log(log(n)), daher der Name) und kann in O(1) Elemente hinzufügen.

In der Praxis muss man das natürlich nicht selber bauen. Redis hat das built-in. Und für jede Sprache gibt’s das sicherlich auch als Library.

HLL wird natürlich bei den “ganz großen” verwendet (Reddit hat hier berichtet, wie sie ihre Views zählten; habe gehört, dass sie es mittlerweile nicht mehr so machen). Diese Datenstruktur ist auch der Grund, warum Video-Views oder Upvote-Counts meistens nicht die genaue Zahl wiederspiegeln. HLL hat eine Fehlerrate von ~2%.

Es gibt von HLL noch weitere Abwandlungen, z. B. HLL++.