この質問は以前にもありましたが、その時点では答えがなかったので、もう一度質問することにしました。
C (C++ ではない) でブルーム フィルターを効率的に実装する必要があります。そのようなものが利用できない場合は、時間がかかりすぎないように良い参照があれば、実装してもかまいません。
このデータ構造を挿入とテストに比率 (1:20k) で使用したいので、主にテスト集約的です。テストするデータは 64 ビット整数です。
質問する
13907 次
5 に答える
16
ここにスタンドアロンのプレーン C ライブラリがあります。これは役に立つかもしれません: https://github.com/jvirkki/libbloom
于 2013-02-13T08:50:33.613 に答える
4
自己宣伝はあまりしませんが、重複するテキスト行を除外するGeanyエディター/IDE用のプラグインを作成しました。これはブルームフィルターを使用します。
実装はCであり、ここGitHubで見つけることができます。これはGPLv3であるため、正確なニーズに応じて、使用できる場合とできない場合があります。
私の実装に関するいくつかのメモ：
- 文字列をフィルタリングするように設計されており、キータイプを抽象化しません。これは、ニーズに合わせてキー処理を変更する必要があることを意味します。
- これは、特徴のないセマンティクスをサポートします。必要に応じて、完全に非確率的な存在テストに実際に使用できます（で
BloomContains使用されるコールバック関数ポインターを参照bloom_filter_new()）。NULL「純粋な」フィルターを取得するには、パスするだけです。 - 文字列ハッシュ関数は、AustinApplebyによるMurmurHash2です。最新のMurmurHash3を評価しましたが、バージョン2の方が操作が簡単でした。
- Geanyエコシステムに適合するために、このコードは全体でGLibタイプを使用します。
パフォーマンスについてはあまり調整されていませんが、問題はないはずです。もちろん、テスト後にフィードバックをいただければ幸いです。
于 2012-06-13T06:59:12.243 に答える
2
Chromium には C++ の 1 つがあります。
于 2012-06-13T02:40:15.333 に答える