java - O(n) の整数のストリームから重複を削除するブルーム フィルター

Question

ブルーム フィルターを作成して、O(n) 時間の複雑さと O(1) 空間の複雑さで整数のストリームから重複要素を削除する方法は? 可能であれば、誰かが私を正しい方向に向けることができれば幸いです?

Answer 1

私はそれがただだと確信しています：

各要素について:

• ブルームフィルターに存在するかどうかを確認します。存在する場合は、重複している可能性があります
• ブルームフィルターに差し込む

これには2つの問題があります。

• 誤検知の可能性がある
• サイズは（一意の）要素の数にある程度依存する必要があるため、これは真の O(1) 空間ではありません (ただし、そう言う人もいます)。そうしないと、要素の数が増えるにつれてエラー率が大幅に増加します。

制約があれば、これらの問題のいずれかを回避できるとは思いません。どちらも、(のみ) ブルーム フィルターを使用する上で不可欠な部分です。

ストリームではなくリストを扱っていた場合、ブルーム フィルターによって取得されたすべての要素を記録することで誤検知を取り除き、代わりに候補リストをチェックしてリストを再度調べます。 '実際の複製です。これはまだ O(n) 時間ですが、明らかに O(1) 空間ではありません。

Answer 2

Google Guava は、ブルーム フィルターの実装を提供します。

ブルームフィルターだけでは十分ではないことに注意してください。ブルームフィルターが数値が含まれていないと主張する場合、それは含まれていません。ただし、番号が既に含まれていると主張する場合は、それが間違っている可能性があります。したがって、確実に別のデータ構造を用意し、ブルームフィルターを使用してそのデータ構造のルックアップ数を減らす必要があります。