私はIpフィルタを開発し、どのようなエスクデータ構造を使っても、どのようにして効率的で高速なBlackListフィルタを開発できるかを推測していました。BlackListを実装する最も効率的な方法
私がやりたいことは、すべての着信/着信接続がブロックされたIPのリストをチェックする必要があります。
IPは散在しており、メモリ使用量は制限されたシステム（家庭用ルータ）で使用したいのでブロックされたリストの数に依存しません。
私は時間があり、ゼロから何かを作ることができます。難しさは私には重要ではありません。 何かを使用できる場合は、何をすべきですか？
このようなシステムのパフォーマンスを向上させる1つの方法は、Bloom Filterを使用することです。これは確率的なデータ構造であり、偽陽性は可能であるが偽陰性は可能ではない、非常に少ないメモリを占有する。
IPアドレスを検索する場合は、まずBloom Filterをチェックインします。ミスがある場合は、すぐにトラフィックを許可することができます。ヒットがある場合は、信頼できるデータ構造（ハッシュテーブルやプレフィックスツリーなど）を確認する必要があります。
「Bloom Filterではヒットしますが、実際には許可された」アドレスの小さなキャッシュを作成することもできます。これはBloom Filterの後で、権限のあるデータ構造の前にチェックされます。
基本的な考え方は、低速パス（IPアドレスが拒否された）を犠牲にして高速パス（IPアドレスが許可されている）を高速化することです。
私はあなたを探しています。 – bratao
ハッシュテーブルは移動する方法です。 検索、挿入、削除のためのO（1）の複雑さが平均化されています。 彼らは木よりも多くのメモリを占有する傾向がありますが、はるかに高速です。
32ビット整数（もちろんIPを32ビット整数に変換することができます）は驚くほど単純で高速です。
ソートされた配列を使用できます。挿入と削除のコストはO（n）ですが、検索はO（log n）です。特にメモリは各ipに対してちょうど4バイトです。 実装は非常に簡単です。恐らく多すぎます。D
バイナリツリーは、検索、挿入、削除のためにO（log n）の複雑さを持ちます。 単純なバイナリツリーでは十分ではありませんが、AVLツリーまたはレッドブラックツリーが必要です。これは実装するのが面倒で複雑な場合があります。AVLツリーとRBTツリーはバランスを取ることができます。不均衡なツリーは、ルックアップのためにO（n）の最悪の時間複雑さを持つため、単純なリンクリストと同じです！
単一でユニークなipの代わりにipの範囲を禁止する必要がある場合は、恐らくRadix Treeと呼ばれるPatricia Trieが必要です。それらは単語辞書とIP辞書用に発明されました。 しかし、うまく書かれていないと、これらの木は遅くなります。 ハッシュテーブルは、簡単なルックアップの方が常に優れています。彼らは本当であるには余りにも速いです:)
今すぐ同期について：
は、アプリケーションの起動時に一度だけのブラックリストを満たしている場合は、あなただけのハッシュテーブル（または基数ツリーを）読んで、プレーンを使用することができますドン」というマルチスレッドとロックに関する問題があります。
非常に頻繁に更新する必要がある場合は、リーダーライターのロックを使用することをお勧めします。
非常に頻繁な更新が必要な場合は、並行ハッシュテーブルを使用することをお勧めします。 警告：あなた自身では書いていない、非常に複雑でバグが多い、Web上の実装を見つける！ 彼らは、新しいプロセッサの（比較的に）新しい原子CAS操作をたくさん使用します（CASはCompare and Swapを意味します）。これらは、メモリ上の32ビットまたは64ビットのフィールドを、ロックを必要とせずに単一のアトミック操作で比較およびスワップできる特別な命令セットまたは命令シーケンスです。 それらを使用することは、プロセッサ、運用システム、コンパイラ、アルゴリズムそのものをよく知っていなければならないので、複雑になる可能性があります。 CASの詳細については、http://en.wikipedia.org/wiki/Compare-and-swapを参照してください。
同時AVL木が発明され、私は本当にこれら:)例えば、http://hal.inria.fr/docs/00/07/39/31/PDF/RR-2761.pdf
は、私はちょうど同時基数木が存在することがわかっについて言いたいことがわからないほど複雑であるた： ftp://82.96.64.7/pub/linux/kernel/people/npiggin/patches/lockless/2.6.16-rc5/radix-intro.pdfそれあまりにも複雑です。
並行ソート配列は存在しません。もちろん、更新のためにリーダライタロックが必要です。
非並行ハッシュテーブルを処理するために必要なメモリ量は、ごくわずかです。各IPに対して、IPとポインタに4バイト必要です。 また、格納するアイテムの数よりも大きな素数でなければならない大きな配列のポインタ（またはいくつかのトリックで32ビットの整数）が必要です。 ハッシュテーブルはもちろん、必要に応じて必要に応じてサイズを変更することもできますが、その素数よりも多くの項目を保存することができますが、検索時間はそれほど長くなりません。
ツリーとハッシュテーブルの両方について、空間の複雑さは線形です。
私はこれがマルチスレッドアプリケーションであり、マルチプロセスアプリケーション（fork）ではないことを望みます。 マルチスレッドでない場合は、メモリの一部を高速で信頼できる方法で共有することはできません。
「最も効率的」とは、定量化するための厳しい用語です。明らかに、無制限のメモリがあれば、すべてのIPアドレスに対してビンがあり、すぐにインデックスに登録できます。
一般的なトレードオフは、Bツリータイプのデータ構造を使用することです。第1レベルのビンは、現在ブロックされているすべてのIPアドレスを含むリストへのポインタおよびそのサイズを格納することができるIPアドレスの最初の8ビットに対して予め設定することができる。この2番目のリストは、不要なmemmove()呼び出しを防ぎ、場合によってはソートされないように埋め込まれます。 （サイズおよびメモリ内のリストの長さを有することは、挿入時間のわずかな高価で、リスト上のインプレースバイナリ検索を可能にする。）例えば
：このように
127.0.0.1 =insert=> { 127 :: 1 }
127.0.1.0 =insert=> { 127 :: 1, 256 }
12.0.2.30 =insert=> { 12 : 542; 127 :: 1, 256 }
オーバーヘッドデータ構造が最小であり、合計ストレージサイズが固定されています。より悪いケースは、明らかに、同じ最高位ビットを有する多数のIPアドレスである。
より具体的になると、大きな助けになります。パフォーマンスが重要なシナリオをいくつか説明します。それが完全に異なる実装をとるだろう。 「散在した」単一のIPをターゲットにしている場合と比べて、全体のIP範囲をターゲットにしています。 – Jon
jonのヒントありがとう、私はさらに指定しました！ – bratao
メモリ使用量が一定の場合は、ブラックリストに入れることができるIPの最大数に制約があります。 –