時間と空間に関して最も良いのはブルームフィルタ、ハッシュテーブル、または辞書ですか？

Question

固定サイズ（8文字）の4000文字列をC＃に格納する必要がありますが、私にはわかりません ブルームフィルタ、ハッシュテーブル、またはディクショナリのスペースと時間については、いずれかが助けてくれたら助けてください

Answer 1

C＃の辞書はハッシュテーブルを使って実装されているので、この質問では実際にはC＃で2つのデータ構造しか持っていません。したがって、DictionaryとHashTableは両方ともハッシュテーブルであるとみなします。それらのうちの1つを使用する場合は、ここで扱う型の安全性とパフォーマンスのために辞書が必要になることがあります。Why is Dictionary preferred over hashtable?しかし、辞書はハッシュテーブルを使用して実装されるため、大きな違いはありません。

しかし実際の問題は、ハッシュテーブル（辞書）とブルームフィルタです。誰かが先に関連する質問をしています。What is the advantage to using bloom filters?彼らはまた、有益な、ブルームフィルターのWikipediaページにリンクしています。https://en.wikipedia.org/wiki/Bloom_filter答えの短いバージョンはブルームフィルターが小さくて速いということです。しかし、彼らはこれに関連するコストを持っています。彼らは完全に正確ではありません。ハッシュテーブルでは、正確な比較のために元の文字列が常に格納されます。最初に値をハッシュすると、これはテーブルのどこに表示されるかを示します。テーブルを調べたら、そこにある値を検索している値と照合します。 Bloomフィルタでは、複数のハッシュを使用して一連の位置を計算します。それらの場所のすべてに1がある場合、見つかった文字列を考慮します。これは、元々は挿入されていない文字列が「発見」されることがあることを意味します。テーブルが小さすぎると、実際に試した文字列がBloomフィルタに表示されるような彩度のポイントに達する可能性があります。挿入しようとしている文字列の数がわかっているので、これを避けるためにテーブルを適切にサイズ変更することができます。

サイズを見てみましょう。数字がきれいに出るように、私はあなたが正確に4096の文字列を持っていると思っています。相対的に衝突の少ないハッシュテーブルを作成するには、少なくともテーブルの文字列数を大きくする必要があります。したがって、現実的には（32ビット（4バイト）ポインタを前提としています）、この場合、テーブルのサイズは4096 * 4バイト= 16K、さらに4096 *（4 + 4 + 8）= 64Kリストノード（次のポインタ+文字列ポインタ）と文字列。したがって、合計でおそらく約80Kです。これは、C＃を使用するほとんどの状況ではおそらくあまりメモリではありません。

ブルームフィルタでは、サイズ計算で目標とするエラーレートを決定する必要があります。 1％の誤り率について言えば、Bloomフィルタに挿入されていない100個の文字列のうち、1個が存在すると誤って表示されることを意味します。挿入された文字列は、挿入されたものとして常に正しく表示されます。方程式m = -n * ln（p）/（ln（2）^ 2）を使用して、最小誤差の大きさを計算することができます。その式において、mはテーブル内のスロットの数であり、pは誤り率であり、nは挿入される文字列の数である。したがって、pを0.01（1％エラー）に設定すると、約9.6 * 4096ビット= 9.6 * 512バイト= 4.8Kとなり、明らかにかなり小さくなります。しかし、本当に、1％はエラー率が高いです。だからもっと現実的には、0.0001％のようなものを、28.8 * 4096bビット= 28.8 * 512バイト= 14.4Kに変換する必要があります。明らかに、それらのいずれかが、ハッシュテーブルに対して計算した80Kよりも実質的に小さい。ただし、ハッシュテーブルのエラーレートは0で、明らかに1％または0.0001％未満です。

実際には、あなたの状況では、少しのスピードと少しの時間を得るための精度を失うことのトレードオフは価値があるかどうかはあなた次第です。現実的には、どちらのオプションも実世界の大多数の状況に対して十分に小さく、十分に速い可能性があります。

Answer 2

.NET 1.0のSystem.Collections.Hashtableは、.NET 2.0で導入されたSystem.Collections.Generic.Dictionaryとまったく同じです。

あなたのキーと値のタイプを指定することで、タイプセーフなので、辞書を使うことをお勧めします。ハッシュテーブルはオブジェクト型だけを取ります。データを取得するたびに文字列にキャストする必要があります。

Answer 3

辞書はあるタイプから別のタイプへのマッピングを表す抽象的なデータ型です。辞書の実装が何であるかは指定されていません。ハッシュテーブル、平衡バイナリ検索ツリー、スキップリスト、または他の多くの構造のいずれかによってサポートされます。辞書はあるタイプの要素を他のタイプと関連付けるため、おそらくここでは適切ではないでしょう。あなたはこれをやっているわけではありません - 要素を格納することだけに関心があります - これはおそらく不適切です。

ブルームをフィルタリングするには、要素がセットに間違いではありませんが、何かがセットでであるかどうかを確認するためにあなたを伝えることができないかどうかをチェックするための良い確率的なデータ構造です。これは、不要なネットワーク読み取りを避けるために、分散システムで一般的に使用されています。各コンピュータは、どのエントリがデータベースにあるのかというBloomフィルタを格納することができ、フィルタによってエントリが除外されている場合、リモートシステムに問い合せないことにより、不要なネットワークコールを明らかにフィルタリングできます。偽陽性は恐らく取引を中断しているかもしれないので、あなたがやろうとしていることはあまり良くありません。

ハッシュテーブルは、しかし、あなたが望むもののための素晴らしいデータ構造です。これは要素の高速検索と挿入をサポートし、実装が良好であればメモリ効率が非常に高くなります。ただし、ソートされた順序で要素を格納することはありません。これはアプリケーションによっては問題になる可能性があります。

ソート順が必要な場合は、考慮する必要がある他の2つの構造があります。最初は平衡二分探索木であり、高速検索と削除をサポートし、要素をソート順に格納します。そこには多くの良い実装があります。事実上すべての良いプログラミング言語が実装されています。もう1つはであり、非常に高速な検索とアクセスをサポートし、ソート順を維持します。これは、文字列の分布に応じて少しスペースが不十分になる可能性がありますが、探しているものと正確に一致する可能性があります。

希望すると便利です。