説明すべての

Question

まず私は、インターネットを散歩して、私はそのアルゴリズムに出くわしたと私はそれが働いたかと思いまして、私はそうthis question.

を読むことを言ってから始めましょう。私はそれを読んだ後、ビットをハッシュして使用することによってビューがどのようにカウントされるのか理解しました。

まだ私がまだ理解していないことは、どのようにして同じビューを再度カウントするのを避けることができるかです。カウント値をインクリメントする前に、ハッシュ値が格納されているかどうかをチェックします。

私たちが1000kアイテムを持っていれば、それはそれほど効率が悪くなりませんか？

Answer 1

HyperLogLogのクールなことは、見たアレイ全体を保存する必要がなく、一意の値でなくてもO(n)であることです。あなたが保存する必要があるものは、はるかに低いoreder O(log(log(n))です。

基本的に、2つのオブジェクトが同じ値を持つ場合、ハッシュは同じになります。これは、先頭のビットも同じであることを意味します。したがって、同じ値を持つ複数のオブジェクトを持つことは、計算にまったく影響しません。

この点も簡単な並列処理を可能にします。母集団を分割し、別々の最大値を計算して後で組み合わせることができます。