5

免責事項：この質問に対する完全に明白な答えはHashSet<string>. それはとてつもなく速く、順序付けられておらず、その値は一意です。

しかし、私はちょうど疑問に思っています.なぜならHashSet<T>、それは変更可能なクラスなので、、、AddなどがありますRemove; したがって、これらの操作を可能にする基礎となるデータ構造が、読み取り操作に関して特定のパフォーマンスを犠牲にするかどうかはわかりません。特に、Contains.

基本的に、 type のオブジェクトのメソッドを提供できる、存在する絶対的に最速のデータ構造は何だろうと思っています。.NET フレームワーク自体の内外。Containsstring

制限に関係なく、あらゆる種類の答えに興味があります。たとえば、ある構造が特定の長さの文字列に制限されたり、問題の領域 (たとえば、可能な入力値の範囲) に応じて最適化されたりする可能性があると想像できます。存在する場合は、それについて聞きたいです。

最後に 1 つ: これを読み取り専用のデータ構造に限定しているわけではありません。明らかに、読み取り/書き込みデータ構造は、読み取り専用ラッパー内に埋め込むことができます。「読み取り専用」という言葉に言及した唯一の理由は、データ構造に追加、削除などを許可する必要がないからです。ただし、それらの機能があれば文句は言いません。

更新：

モロンの答えは、私が探している種類のものの優れた例です。Trie *は、次の理由から間違いなく大きな可能性のように思えます: someHashSet<T>.Containsの機能に依存します。これは、私が知る限り、.NET ではデフォルトで O(n)** です。つまり、文字列内のすべての文字を調べて、 またはを返す必要があります。a の場合、 の戻り値のみが O(n) を使用して決定されます。の戻り値は、はるかに迅速に返される可能性があります。GetHashCodeIEqualityComparer<string>HashSet<string>.Containstrue falseTrietruefalse

これはもちろん仮説です。HashSet<string>これまでのところ、a at に勝る .NET の Trie 実装を書いたり、見つけたりしたことはありませんContains(ただし、自分で書いた実装は、アルファベット 'a' から 'z' に非常に近いものでした)。私はただ言っている、それは可能だと思われる.

*ちなみに、そのリンクは、別の興味深い/同様の可能性にもつながりました: DAWG .
**ここで「n」は文字列の長さを指しています。

4

4 に答える 4

2

試行Containsは、特に有限のアルファベットからの文字列の場合に適しています。文字列 s が与えられた場合、トライの Contains の時間計算量は O(|s|) (|s| = s の長さ) であり、最適です。

于 2010-06-17T17:33:31.703 に答える
1

ハッシュ テーブルは、ルックアップのために償却された O(1) です。それ以上のことはできません。O(1/n) アルゴリズムは永久運動デバイスです。それらの動作を低下させる原因は 2 つだけです。

  • 多くの衝突を引き起こす貧弱なハッシュ関数。最悪の場合、ルックアップが O(n) に縮退します。文字列に問題はありません。文字列は非常にうまくハッシュされます。String.GetHashCode() は素晴らしい仕事をします。
  • 初期に追加された多くの削除されたアイテムで大幅に変更されたコレクション。これにより、反復子によってスキップされる必要がある空のハッシュ バケットが多数発生する可能性があります。非常にまれですが、O(n) への劣化は技術的に可能です。簡単な回避策は、参照を再割り当てしてコレクションを再構築することです ( table = new HashSet(table); のように)。

この種の問題はまれです。(ハッシュ関数を除いて) それらを事前に設計するのではなく、プログラムのパフォーマンスの問題を検出したときにのみそれらを検討し始めます。

于 2010-06-17T18:18:03.267 に答える
1

あなたの疑問は別として、 Hashset は最速のコレクションです。

基礎となる Hashtable は O(1) 読み取り/書き込みアクセスを許可するため、より高速な方法はありません

于 2010-06-17T16:25:25.207 に答える
1

ハッシュ コンテナーは、挿入と取得で O(1) に近づくため、桁違いの観点からすると、それよりもはるかに優れたものはありません。

ハッシュ コンテナー内での時間の経過に伴うパフォーマンスは、ハッシュ関数が提供する分散の良さと、それを計算する速度の 2 つに関連します。これらは同等ではありません - 不十分に分散された関数 (多くの衝突が発生する) は、低速ですがより優れた分散ハッシュ関数よりもパフォーマンスに大きな影響を与えます。

したがって、計算が非常に高速な完全なハッシュ関数を考え出すことができれば、それは改善になります. 特定の方法でデータを制約すると、それが容易になる可能性があります。しかし、あなたが思いついたものは、すでに存在するものほど良くはありません。

于 2010-06-17T17:00:27.807 に答える