c# - 単語のコレクションに最適なデータ構造は何ですか?

Question

私は約 170,000 語のコレクションを持っており、それらに対して多くの操作を実行しています。最も一般的なものは、 StartsWith、EndsWith、およびContainsです。長さのチェックもしっかりしています。

私はもともとこの情報をに保存していましたが、このタイプのデータの方が高速であると考え List<string>たため、に切り替えました。HashSet<string>

私が説明したことに基づいて、HashSet はこのデータに最適なタイプのコレクションですか?

score 5 · Accepted Answer

トライは、文字列を格納し、必要なテキスト検索操作を実行するための非常に優れたデータ構造です。これは、Luceneなどの検索エンジンで使用する文字列値のインデックス作成に一般的に使用されるデータ構造です。

通常、トライは、非常に効率的な検索を可能にするプレフィックスツリーとして説明されます。データ構造の接尾辞木のバリエーションは、検索で終了するときに非常に効率的です。

おそらく、トライにデータを入力するとき、およびトライを検索するときに文字列を逆にするだけで、プレフィックスツリーとサフィックスツリーの両方に同じトライ実装を使用できます。

score 2 · Accepted Answer

私はあなたが一致するものを見つけようとしていると仮定しています which StartsWith、EndWithまたはContainsいくつかの検索語。その場合、それListは理想的ではないという点で正しいです。私Hashsetはこれ以上良いとは思いません。

試してみてください。私はそれを構築しませんが、問題空間についてのコンテキストがあれば。このアルゴリズムでは、単語を最初の部分文字列でグループ化します。最初の文字に基づいて単語をグループ化し、次に 2 番目の文字でサブグループ化する、というようにします。

過去にこれを行ったとき、Lookupクラスと実装の両方を利用しましたDictionary<string, List<string>>。

私が使用したアルゴリズムは大まかに

var dictionary = new Dictionary<int, Lookup<string, string>>();
for (int i = 1; i < maxWordLength; i++)
{
    // get all words with i or more letters
    dictionary.Add(i, words.ToLookup(w => w.Substring(i)));
}

そして、次のような単語を見つけます

var word = "TestWord";
var matches = dictionary[word.Length][word];

また必要な場合は、おそらくそれらにも多くのインデックス構造が必要にEndsWithなります。Contains

score 2 · Accepted Answer

あなたが言及した操作はすべて、コレクションの個々の要素に対して行われているため、要素が実際にどのタイプのコレクションから来ているのかはまったくわかりません。

コレクション型で考慮すべき重要なことは、コレクション全体をどのように操作するかということです。項目を頻繁に挿入するか、頻繁に削除するかです。各要素を順番に取得したいですか、それともコレクションの特定の部分により頻繁にアクセスしたいですか。コレクションに重複する要素を含めることはできますか? メンバーシップを確認する必要がありますか? それらを処理する順序は重要ですか?

これらは、さまざまなコレクションの種類について情報に基づいた決定を下すために答える必要がある種類の質問です。

score 1 · Accepted Answer

これはLuceneの仕事のように聞こえます。ただし、独自のアルゴリズム (それが何であれ) を実装することに決めた場合は、Parallel.ForEach と PLINQ で C# の強力な並列ループ構造を利用することをお勧めします。

データ並列処理 (タスク並列ライブラリ)

パラレル LINQ (PLINQ)

すなわち

var source = Enumerable.Range(100, 20000);

// Result sequence might be out of order.
var parallelQuery = from num in source.AsParallel()
                    where num % 10 == 0
                    select num;

score 0 · Accepted Answer

テストを実行しましたが、期待した答えが得られませんでした。List と HashSet と AsParallel はほぼ同じです (ただし、2 コアマシンのみ)。.NET 4.0 と 600,000 語のリスト。

最初のコメントを繰り返します。迷ったらテスト。l はリスト、h はハッシュセットです。

Debug.WriteLine("lWords.Count hWords.Count " + lWords.Count.ToString() + " " + hWords.Count.ToString());
Stopwatch SW = new Stopwatch();
SW.Restart();
Debug.WriteLine("H count " + hWords.Where(value => value.StartsWith("s")).Count().ToString());
SW.Stop();
Debug.WriteLine("H time " + SW.ElapsedMilliseconds.ToString());
SW.Restart();
SW.Stop();
Debug.WriteLine("Start Stop " + SW.ElapsedMilliseconds.ToString());
SW.Restart();
Debug.WriteLine("L count " + lWords.Where(value => value.StartsWith("s")).Count().ToString());
SW.Stop();
Debug.WriteLine("L time " + SW.ElapsedMilliseconds.ToString());
SW.Restart();
Debug.WriteLine("H count " + hWords.Where(value => value.StartsWith("s")).Count().ToString());
SW.Stop();
Debug.WriteLine("H time " + SW.ElapsedMilliseconds.ToString());
SW.Restart();
Debug.WriteLine("L count " + lWords.AsParallel().Where(value => value.StartsWith("s")).Count().ToString());
SW.Stop();
Debug.WriteLine("L time parallel " + SW.ElapsedMilliseconds.ToString());
SW.Restart();
Debug.WriteLine("H count " + hWords.AsParallel().Where(value => value.StartsWith("s")).Count().ToString());
SW.Stop();
Debug.WriteLine("H time parallel " + SW.ElapsedMilliseconds.ToString());
Debug.WriteLine("");

output:
lWords.Count hWords.Count 667309 667309
H count 45851
H time 283
Start Stop 0
L count 45851
L time 285
H count 45851
H time 364
L count 45851
L time parallel 307
H count 45851
H time parallel 344

score 0 · Accepted Answer

リストが静的である場合、オーバーヘッドが最も低いため、おそらく文字列の配列が最適です。

次に、複数のスレッドを使用します。

c# - 単語のコレクションに最適なデータ構造は何ですか?

6 に答える 6

Related

Reference