14

特定の文字列が他の文字列のセットに含まれていることを確認する必要があります。

private bool Contains(string field)
{
   return this.Fields.Contains(field); // HashSet<string> local property
}

コンテナの1つのタスクだけが、いくつかの文字列を保持し、別の文字列が入っているかどうかを確認する場合に使用するのに最適なタイプのコンテナは何ですか？

4

2 に答える 2

39

HashSetは機能しますか？もちろん。しかし、それはあなたが尋ねた質問ではありません。あなたは可能な限り最速のルックアップを求めました。

それは可能な限り最速ですか？いいえ、もちろんそうではありません。

まず、「最速」について話すために、「最速」が何を意味するかを正確に説明する必要があります。意味は：

  • 最悪の場合の最小のタイミング
  • 多くのタイミングで平均化された最小の平均タイミング
  • 特定の使用パターンが与えられた場合の最小の平均タイミング
  • 他の何か

？「可能な限り最速」の意味を正確に明確にしてください。可能な限り最速があなたにとって何を意味するかを正確に知っている場合にのみ、理論的に可能な限り最速のアルゴリズムを考案することができます。

たとえば、コンパイラを作成しているとします。コンパイラで常に実行しなければならないことは、特定の文字列が文字列のリストに含まれているかどうかを確認することです。おそらく、文字列がキーワードであるかどうかを確認しているので、指定された文字列がセット{"int"、 "double"、 "for"、 "foreach"、"class"..の中にあるかどうかを調べる必要があります。 }

それらをハッシュセットに入れて、まともなパフォーマンスを得ることができます。しかし、可能な限り最高のパフォーマンスが必要な場合は、はるかに優れたパフォーマンスを実現できます。たとえば、数十億行の既存のソースコードを分析して、最も一般的なキーワードと最も一般的でないキーワードを見つけ、（1）次のようなものを迅速に拒否するように最適化されたカスタムハッシュテーブルを作成できます。キーワードではなく、（2）他のキーワードを認識することを犠牲にして、最も一般的なキーワードを迅速に認識します。

これには静的分析が必要であることに注意してください。通常のケースではうまく機能しますが、まれなキーワードがたくさん使用されているまれなケースではパフォーマンスが低下します。私たちが取ることができる別のアプローチは、特定の文字列が頻繁に検索されているときに動的に識別されるセルフチューニングハッシュテーブルを作成することです。

たとえば、JScriptランタイムの実装を作成している場合を考えてみてください。文字列のセットから文字列を頻繁に検索する必要があります。

for(i = 0; i < 10; ++i) { foo.bar(i); }

ここでは、「foo」で識別されるオブジェクト内の文字列「bar」を10回検索する必要があります。そのルックアップを実装する「foo」内のハッシュテーブルは、「bar」が使用されたことをループで最初に通知するため、ハッシュテーブル構造を動的に微調整して、ループで2回目はルックアップが高速になるようにします。これは、JScriptの実装で採用した戦略です。

さて、これはループのケースを最適化しますが、このケースは潜在的にそれよりも遅くなります： 

for(i = 0; i < 10; ++i) { foo.bar(i); foo.blah(i); foo.abc(i); }

これ以上の分析を行わず、「ねえ、このハッシュテーブルを3回再最適化しただけで、今度はすべてをやり直します。そのままにしておく必要があるかもしれません」と気付いたからです。

私たちにとって幸いなことに、私たちはあなたのように、可能な限り最速のルックアップを探していませんでした。適度に高速なルックアップのみを探していました。

可能な限り最速のルックアップのための使用例を注意深く完全に説明できますか？ルックアップを高速化するために使用できるアルゴリズムはたくさんありますが、それらは非常に複雑になります。

于 2010-02-14T18:04:19.267 に答える
14

はい、HashSetは、キーと値を必要とする辞書とは異なり、検索する値が1つ含まれているため、これに最適です。

于 2010-02-13T20:50:51.103 に答える