2012-05-10 16 views
3

フック語は、先頭または末尾に1文字を追加して新しい単語を作成できる単語です。単語のリストに「フック単語」を見つける効率的な方法は?

私はかなり大きな単語リスト(約170k)を持っています。私は5つのランダムフック単語を選択したいと思います。問題は、私が使っている方法が非常に遅いことです。以下を参照してください:

Random rnd = new Random(); 
var hookBases = (from aw in allWords //allWords is a List<string> 
       from aw2 in allWords 
       where aw2.Contains(aw) 
         && aw2.Length == aw.Length + 1 
         && aw[0] == 'c' 
       select aw).OrderBy(t => rnd.Next()).Take(5); 

私はあきらめて、それを殺す前に、それが数分間スピンhookBaseから何かをアクセスしようとします。

誰も私がこれをやろうとしている間違いを見ることができますか?もっと効率的な提案はありますか?

答えて

6

まず、効率的な検索のために、すべての単語はHashSet<string>で、List<string>ではありません。

これが完了したら、ハッシュセットを繰り返して、最初または最後の文字を削除すると新しい有効な単語が得られるかどうかを確認します。それはあなたのフックワードです。

HashSet<string> result = new HashSet<string>(); 
foreach (string word in allWords) { 
    string candidate = word.Substring(0, word.Length - 1); 
    if (allWords.Contains(candidate)) { result.Add(candidate); } 
    candidate = word.Substring(1, word.Length - 1); 
    if (allWords.Contains(candidate)) { result.Add(candidate); } 
} 

あなたはLINQでこれを行うにしたい場合:

List<string> hookWords = allWords 
    .Select(word => word.Substring(0, word.Length - 1)) 
    .Concat(allWords.Select(word => word.Substring(1, word.Length - 1))) 
    .Distinct() 
    .Where(candidate => allWords.Contains(candidate)) 
    .ToList(); 

は、それがオンラインで作業を参照してください:ideone

+0

速いです。ありがとう! –

+0

@AbeMiessler:重複を避けるために「Distinct」を追加しました。 –

+0

おそらくコレクションに非常に多くのアイテムがあるので、LINQを使ってLINQを使用したくないでしょう。そのオーバーヘッドは増加し、理想的ではありません。 –

-1

私は最近、似たような行っています。私はlinqで試して、正規表現を持つ.netアセンブリをddbbとストアドプロシージャに保存しました。 最も効率的な方法はストアドプロシージャを使用することでした。トランザクションエンジンは、この種の操作のためにMicrosoftによって高度に最適化されています。

お礼

関連する問題