現在のコードでは、Dictionary の特別な機能をまったく利用していません。 / SortedDictionary / HashSet コレクション、List を使用するのと同じ方法で使用しています。 .そのため、パフォーマンスに違いは見られません。
文字列の最初の数文字がキーで、文字列のリストが値であるインデックスとして辞書を使用する場合、検索文字列から、一致する可能性のある文字列のコレクション全体の小さな部分を選択できます。 /P>
これをテストするために、以下のクラスを作成しました。 100 万の文字列を入力して 8 文字の文字列で検索すると、約 3 ミリ秒ですべての可能な一致をリッピングします。 1文字列で検索するのは最悪ですが、最初の1000件を約4msで検索します。 1 つの文字列のすべての一致を見つけるには、約 25 ミリ秒かかります。
このクラスは、1、2、4、および 8 文字のキーのインデックスを作成します。特定のデータと検索対象を見ると、条件に合わせて最適化するために作成するインデックスを選択できるはずです。
public class IndexedList {
private class Index : Dictionary<string, List<string>> {
private int _indexLength;
public Index(int indexLength) {
_indexLength = indexLength;
}
public void Add(string value) {
if (value.Length >= _indexLength) {
string key = value.Substring(0, _indexLength);
List<string> list;
if (!this.TryGetValue(key, out list)) {
Add(key, list = new List<string>());
}
list.Add(value);
}
}
public IEnumerable<string> Find(string query, int limit) {
return
this[query.Substring(0, _indexLength)]
.Where(s => s.Length > query.Length && s.StartsWith(query))
.Take(limit);
}
}
private Index _index1;
private Index _index2;
private Index _index4;
private Index _index8;
public IndexedList(IEnumerable<string> values) {
_index1 = new Index(1);
_index2 = new Index(2);
_index4 = new Index(4);
_index8 = new Index(8);
foreach (string value in values) {
_index1.Add(value);
_index2.Add(value);
_index4.Add(value);
_index8.Add(value);
}
}
public IEnumerable<string> Find(string query, int limit) {
if (query.Length >= 8) return _index8.Find(query, limit);
if (query.Length >= 4) return _index4.Find(query,limit);
if (query.Length >= 2) return _index2.Find(query,limit);
return _index1.Find(query, limit);
}
}
列にインデックスがあるに違いないので、SQL サーバーは O(n) ではなく O(log(n)) 操作で比較できます。 SQL サーバーの動作を模倣するには、並べ替えられたコレクションを使用して、s>=クエリとなるすべての文字列 s を検索し、s で始まらない値が見つかるまで値を調べてから、値に対して追加のフィルターを実行します。これは、範囲スキャン (Oracle) またはインデックス シーク (SQL サーバー) と呼ばれるものです。
これは、テストしていないため、無限ループに陥ったり、1 回限りのエラーが発生したりする可能性が非常に高いサンプル コードですが、アイデアは理解できるはずです。
// Note, list must be sorted before being passed to this function
IEnumerable<string> FindStringsThatStartWith(List<string> list, string query) {
int low = 0, high = list.Count - 1;
while (high > low) {
int mid = (low + high) / 2;
if (list[mid] < query)
low = mid + 1;
else
high = mid - 1;
}
while (low < list.Count && list[low].StartsWith(query) && list[low].Length > query.Length)
yield return list[low];
low++;
}
}
「で始まる」を行っている場合は、序数の比較のみを気にし、コレクションを（再び序数順に）並べ替えることができます。リストに値を入れることをお勧めします。次に、バイナリ検索を実行して、正しいプレフィックスで始まる最初の値を見つけ、リストを下に移動して、一致しない最初の値まで直線的に結果を生成します。 正しい接頭辞から始めてください。
実際、接頭辞で始まらない最初の値に対して別のバイナリ検索を実行できる可能性があるため、開始点と終了点が得られます。次に、長さの基準をその一致部分に適用するだけです。 （それが賢明なデータであれば、接頭辞の一致によってほとんどの候補値が取り除かれることを願っています。）接頭辞で始まらない最初の値を見つける方法は、辞書編集的に最初の値を検索することです。しません。 「ABC」のプレフィックスを付けて、「ABD」を検索します。
これはどれもLINQを使用しておらず、特定のケースに非常に固有のものですが、うまくいくはずです。意味をなさないものがある場合はお知らせください。