このコードを高速化するにはどうすればよいですか？

Question

私はここに私の仕事のために非常に遅いが働く機能（それは10〜100倍高速である必要があります）

を持っているコード

List<string[]> sequencesは、単語の配列の配列です

public long Support(List<string[]> sequences, string[] words) 
{ 

      var count = 0; 
      foreach (var sequence in sequences) 
      { 
       for (int i = 0; i < sequence.Length - words.Length + 1; i++) 
       { 
        bool foundSeq = true; 
        for (int j = 0; j < words.Length; j++) 
        { 
         foundSeq = foundSeq && sequence[i + j] == words[j]; 
        } 
        if (foundSeq) 
        { 
         count++; 
         break; 
        } 
       } 
      } 

      return count; 
} 

public void Support(List<string[]> sequences, List<SequenceInfo> sequenceInfoCollection) 
{ 
    System.Threading.Tasks.Parallel.ForEach(sequenceInfoCollection.Where(x => x.Support==null),sequenceInfo => 
    { 
     sequenceInfo.Support = Support(sequences, sequenceInfo.Sequence); 
    }); 

} 

です。この配列は、通常250k +の行を含んでいます。各行は約4-7語です。 string[] wordsは、カウントしようとしている単語の配列です（すべての単語が少なくとも1回は連続しています）。

問題はfoundSeq = foundSeq && sequence[i + j] == words[j];です。このコードは、すべての実行時間の大部分を占めます（Enumerable.MoveNextが2位）。私は配列内のすべての単語をハッシュしたい。数字は文字列よりも速く比較されます。私はそれが性能の30％〜80％を得るのを助けることができると思う。しかし、私は10倍が必要です！私は何ができますか？それがaprioryアルゴリズムの一部であることを知りたければ。

---

サポート機能チェックの単語シーケンスは、シーケンスのリスト内の任意の順序一部であり、どのくらいの時間をカウントします。

Answer 1

クヌース - モリス - プラット法

Knuth-Morris-Pratt文字列検索アルゴリズム（またはKMPアルゴリズム）は、不一致が発生した場合に、単語自体が十分な情報を具現化するという観察を利用して、主な「文字列」S内の「単語」Wの出現を検索する。次の一致がどこから始まるかを決定し、以前に一致した文字の再検査をバイパスする。

アルゴリズムはDonald KnuthとVaughan Prattによって1974年に、またJames H. Morrisによって独立して考案されました。 3は、ウィキペディアから1977年

---

に共同でそれを出版：https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

これはあなたが作るべき改善点の一つです。小さな違いがあります。コード内の「単語」は、アルゴリズムの用語では「文字」です。あなたの「単語」配列はKMPの単語です。

「abc def ghi jkl」を検索し、「abc def ghi」とすでに一致していますが、次の単語が一致しない場合は、3つの位置にジャンプできます。

Search: abc def ghi jkl 
Text:  abc def ghi klm abc def ghi jkl 
i=0:  abc def ghi jkl? 
skip 2:  XXX XXX <--- you save two iterations here, i += 2 
i=2:     abc? 
i=3:      abc? ... 

Answer 2

私が作る最初の最適化は初期の失敗です。あなたの内部ループは、それが失敗したことを知っていても、そしてブール論理の不必要なビットを行っていても、シーケンス全体にわたって続きます。

代わり

for (int j = 0; j < words.Length; j++) 
    { 
     foundSeq = foundSeq && sequence[i + j] == words[j]; 
    } 

、ちょうどこの（または同等品）を実行します：あなたのコードはこれです

for (int j = 0; j < words.Length; j++) 
    { 
     if (sequence[i + j] != words[j]) 
     { 
      foundSeq = false; 
      break; 
     } 
    } 

それはdoesnの場合、これは（あなたが最初の単語でドロップアウトしますあなたの比較の大部分を保存します結果が偽であることを知ったときに比較を続ける代わりに、一致しない）。それは、各シーケンスの個々の単語の出現が低いと予想した場合（たとえ、英語テキストのページで文章を見つけているとしたら）、あなたが探している10倍の違いを作ることさえできます。

Answer 3

理論的には、各シーケンスを連結し、部分文字列一致を使用することができます。私は今、手元にコンパイラを持っていないので、私はそれが実際にパフォーマンスを改善するかどうかをテストすることはできませんが、これは一般的な考え方です：コンピュータで

List<string> sentences = sequences.Select(seq => String.Join(" ", seq)); 
string toMatch = String.Join(" ", words); 

return sentences.Count(sentence => sentence.Contains(toMatch));