私は
List<string>
1500本の弦で。次のコードを使用して、文字列 prefixText で始まる文字列のみを抽出しています。
foreach(string a in <MYLIST>)
{
if(a.StartsWith(prefixText, true, null))
{
newlist.Add(a);
}
}
これはかなり速いですが、Googleを高速で探しています。今私の質問は、リストをアルファベット順に並べてから、文字ごとに比較すると、これをより速くすることができますか? または、これを高速化するための他の提案はありますか?
したがって、1500 は実際には膨大な数ではありません。おそらく、ソートされたリストでのバイナリ検索で十分でしょう。それにもかかわらず、プレフィックス検索の最も効率的なアルゴリズムは、Trie または Prefix Tree という名前のデータ構造に基づいています。参照: http://en.wikipedia.org/wiki/Trie
次の図は、アイデアを非常に簡単に示しています。
C# の実装については、たとえば、.NET DATA STRUCTURES FOR PREFIX STRING SEARCH AND SUBSTRING (INFIX) SEARCH TO IMPLEMENT AUTO-COMPLETION AND INTELLI-SENSEを参照してください。
最小限のデータ容量と高いパフォーマンスを実現するために、非常に多くのアプローチが分析されました。まず、すべてのプレフィックスはディクショナリに格納されます: キー - プレフィックス、値 - プレフィックスに適した項目。
このアルゴリズムの簡単な実装は次のとおりです。
public class Trie<TItem>
{
#region Constructors
public Trie(
IEnumerable<TItem> items,
Func<TItem, string> keySelector,
IComparer<TItem> comparer)
{
this.KeySelector = keySelector;
this.Comparer = comparer;
this.Items = (from item in items
from i in Enumerable.Range(1, this.KeySelector(item).Length)
let key = this.KeySelector(item).Substring(0, i)
group item by key)
.ToDictionary( group => group.Key, group => group.ToList());
}
#endregion
#region Properties
protected Dictionary<string, List<TItem>> Items { get; set; }
protected Func<TItem, string> KeySelector { get; set; }
protected IComparer<TItem> Comparer { get; set; }
#endregion
#region Methods
public List<TItem> Retrieve(string prefix)
{
return this.Items.ContainsKey(prefix)
? this.Items[prefix]
: new List<TItem>();
}
public void Add(TItem item)
{
var keys = (from i in Enumerable.Range(1, this.KeySelector(item).Length)
let key = this.KeySelector(item).Substring(0, i)
select key).ToList();
keys.ForEach(key =>
{
if (!this.Items.ContainsKey(key))
{
this.Items.Add(key, new List<TItem> { item });
}
else if (this.Items[key].All(x => this.Comparer.Compare(x, item) != 0))
{
this.Items[key].Add(item);
}
});
}
public void Remove(TItem item)
{
this.Items.Keys.ToList().ForEach(key =>
{
if (this.Items[key].Any(x => this.Comparer.Compare(x, item) == 0))
{
this.Items[key].RemoveAll(x => this.Comparer.Compare(x, item) == 0);
if (this.Items[key].Count == 0)
{
this.Items.Remove(key);
}
}
});
}
#endregion
}
PLINQ (Parallel LINQ)を使用して実行を高速化できます。
var newList = list.AsParallel().Where(x => x.StartsWith(prefixText)).ToList()
アルファベット順のリストがある場合は、バイナリ検索のバリエーションを使用して、はるかに高速にすることができます。
開始点として、これはプレフィックスに一致する文字列の 1 つのインデックスを返すため、リストを前後に見て残りを見つけることができます。
public static int BinarySearchStartsWith(List<string> words, string prefix, int min, int max) {
while (max >= min) {
int mid = (min + max) / 2;
int comp = String.Compare(words[mid].Substring(0, prefix.Length), prefix);
if (comp < 0) {
min = mid + 1;
} else if (comp > 0) {
max = mid - 1;
} else {
return mid;
}
}
return -1;
}
int index = BinarySearchStartsWith(theList, "pre", 0, theList.Count - 1);
if (index == -1) {
// not found
} else{
// found
}
注: 比較するどの文字列よりも長い接頭辞を使用すると、文字列が破損するため、それをどのように処理するかを検討する必要がある場合があります。
通常、1500 は少なすぎます。
問題の単純な分割と征服と並行して検索できます。リストの各半分を 2 つ (または 3 つ、4 つ、...、の部分に分割) の異なるジョブ/スレッドで検索します。
または、代わりに (バイナリではない) ツリーに文字列を格納します。O(log n)になります。
アルファベット順にソートすると、バイナリ検索を実行できます（前のものと同じソート）
本当に最速の方法は、1500 個の文字列から可能なすべてのプレフィックスを含む辞書を生成し、空でないものを返す可能性のあるすべての検索の結果を効果的に事前計算することだと思います。検索は、O(1) 時間で完了する単なる辞書検索になります。これは、速度のためにメモリ (および初期化時間) をトレードするケースです。
private IDictionary<string, string[]> prefixedStrings;
public void Construct(IEnumerable<string> strings)
{
this.prefixedStrings =
(
from s in strings
from i in Enumerable.Range(1, s.Length)
let p = s.Substring(0, i)
group s by p
).ToDictionary(
g => g.Key,
g => g.ToArray());
}
public string[] Search(string prefix)
{
string[] result;
if (this.prefixedStrings.TryGetValue(prefix, out result))
return result;
return new string[0];
}
StartsWith を呼び出す前に最初の文字を比較することで、少し高速化できます。
char first = prefixText[0];
foreach(string a in <MYLIST>)
{
if (a[0]==first)
{
if(a.StartsWith(prefixText, true, null))
{
newlist.Add(a);
}
}
}
私への質問は、これを 1 回または複数回行う必要があるかどうかです。
StartsWithPrefix リストが 1 回しか見つからない場合は、元のリストをそのままにしてmyList.Where(s => s.StartsWith(prefix)). これはすべての文字列を一度に調べるので、O(n)
StartsWithPrefix リストを数回検索する必要がある場合、または元のリストに文字列を追加または削除して StartsWithPrefix リストを更新する場合は、元のリストを並べ替えてバイナリ検索を使用する必要があります。しかし、これはsort time + search time = O(n log n) + 2 * O(log n)
二分探索法を行った場合は、プレフィックスが最初に出現したインデックスと、検索によって最後に出現したインデックスを見つけることができます。次にmySortedList.Skip(n).Take(m-n)、n が最初のインデックスで m が最後のインデックスである場合に実行します。
ちょっと待ってください、私たちは間違ったツールを使っています。トライを使おう！すべての文字列をリストではなく Trie に入れる場合は、プレフィックスを付けて Trie をたどり、そのノードの下にあるすべての単語を取得するだけです。
Dictionary を実装して結果を比較してみましたか? または、エントリをアルファベット順に並べる場合は、バイナリ検索を試してください。
私はLinqを使用して行きます：
var query = list.Where(w => w.StartsWith("prefixText")).Select(s => s).ToList();