如何使此代碼更快？

我有一個工作很慢的我的任務功能（它必須是快10-100倍）如何使此代碼更快？

這裏是代碼

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); 
    }); 

}

哪裏List<string[]> sequences是文字的數組的數組。這個數組通常包含250k +行。每行約4-7個字。 string[] words是我們嘗試計數的一組單詞（所有單詞至少包含一次）。

問題是foundSeq = foundSeq && sequence[i + j] == words[j];。此代碼佔用了大部分執行時間（Enumerable.MoveNext位於第二位）。我想散列我的數組中的所有單詞。數字比字符串更快，對吧？我認爲它可以幫助我獲得30％-80％的表現。但我需要10倍！我能做什麼？如果你想知道它是apriory算法的一部分。

支持函數檢查單詞序列是否是序列列表中的任意序列的一部分並計數多少次。

來源

2012-05-08 Neir0

請用相應的語言標籤進行標記。 – Mat

我建議您將您要解決的問題的描述移動到代碼上方。 –

@Hosam Aly只是序列中的字（字符串[]字）的計數（列表序列） – Neir0

克努特莫里斯普拉特算法

在計算機科學，Knuth-Morris-Pratt字符串搜索算法（或KMP算法）通過使用以下觀察結果來搜索主「文本串」S內的「單詞」W的出現：當發生不匹配時，該單詞本身體現足夠的信息確定下一場比賽可以開始的位置，從而繞過對先前匹配的字符的重新檢查。

該算法由Donald Knuth和Vaughan Pratt於1974年構思，並由James H. Morris獨立完成。這三個聯合出版它於1977年

維基百科：https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

這是你應該做的改進之一。有一點點不同：代碼中的「單詞」是算法術語中的「字符」;你的「單詞」數組是KMP中的一個詞。

這個想法是，當您搜索「abc def ghi jkl」，並且已經匹配「abc def ghi」時，但下一個單詞不匹配時，您可以跳轉三個位置。

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? ...

來源

2012-05-08 16:05:24

我會做的第一個優化是早期失敗。即使你知道它失敗了，你的內部循環也會繼續執行整個序列，並且你正在做一些不必要的布爾邏輯。您的代碼是這樣的：

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; 
     } 
    }

這將節省您大部分的比較（你將在第一個字退出，如果它不不匹配，而不是繼續比較，當你知道結果是錯誤的）。如果您希望每個序列中的單詞出現率很低（如果您在一頁英文文本中找到句子），它甚至可能會使您尋找的差異達到十倍。

來源

2012-05-08 11:41:05

理論上，你可以連接每個序列並使用子串匹配。我不手邊有一個編譯器現在，所以我不能測試它是否確實會提高性能，但是這是總體思路：

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

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

來源

2012-05-08 11:43:48

如何使此代碼更快？

回答

相關問題