Algorithmen und Datenstrukturen · Senior · Frage 11 von 75
Was schätzt HyperLogLog, und warum ist es beliebt?
- 1Den Median eines Streams in einem einzigen Durchlauf
- 2Die Zahl verschiedener Elemente, in wenigen Kilobyte
- 3Die häufigsten Elemente mit genauen Zählungen
Antwort zeigen
Richtige Antwort: Die Zahl verschiedener Elemente, in wenigen Kilobyte
Erklärung
Es hasht Elemente und merkt sich pro Bucket die längste Folge führender Nullen; eine Folge von k Nullen deutet auf etwa 2ᵏ verschiedene Werte hin. Mit etwa 12 KB liegt der Fehler bei grob 1 %. Redis PFCOUNT und Analytics-Systeme nutzen es für eindeutige Besucher.