Erläuterung zu HyperLogLog Algorithmus

Question

allererst mich mit den Worten beginnen zu lassen, dass ich this question.

So las, wie ich über das Internet schlendere und ich kam in diesem Algorithmus und ich frage mich, wie es funktioniert. Nachdem ich darüber gelesen hatte, verstand ich, wie es die Ansichten durch Hashing und Verwendung von Bits zählt.

Was ich noch nicht ganz verstehe, ist, wie man sicher vermeiden kann, die gleiche Ansicht wieder zu zählen. Speichern wir jeden Hash-Wert, den wir finden, und bevor wir den Zählungs-Check inkrementieren, wenn er bereits in unserem Array existiert oder was auch immer?

Macht das nicht viel weniger effizient, wenn wir 1000k + Elemente haben?

Answer 1

Die coole Sache über HyperLogLog ist, dass Sie nicht das gesamte Array, das Sie gesehen haben, die O(n) wäre, und nicht einmal die eindeutigen Werte speichern müssen. Was Sie speichern müssen, ist der von O(log(log(n)), der viel niedriger ist.

Wenn zwei Objekte denselben Wert haben, ist der Hashwert identisch. Dies bedeutet, dass die führenden Bits auch gleich sind. Wenn also mehrere Objekte mit demselben Wert verwendet werden, wirkt sich dies nicht auf die Berechnung aus.

Diese Tatsache ermöglicht auch eine einfache Parallelität - Sie können Ihre Population teilen und die Max separat berechnen, indem Sie sie später kombinieren, indem Sie das Maximum Ihrer separaten Maxes berechnen.