1

私のタスクには非常に遅い機能があります（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単語の配列の配列はどこにありますか。通常、この配列には 25 万行以上が含まれます。各行は約 4 ～ 7 語です。 string[] wordsカウントしようとしている単語の配列です (すべての単語が少なくとも 1 回連続して含まれます)。

問題はfoundSeq = foundSeq && sequence[i + j] == words[j];. このコードは、すべての実行時間のほとんどを占めます (2 番目の Enumerable.MoveNext)。配列内のすべての単語をハッシュしたい。数値は文字列よりも速く比較されますよね? パフォーマンスの 30% ～ 80% を達成するのに役立つと思います。しかし、私は10倍が必要です！どうすればいいですか？知りたい場合は、アプリオリアルゴリズムの一部です。

サポート関数は、単語シーケンスがシーケンス リスト内の任意のシーケンスの一部であるかどうかをチェックし、その回数をカウントします。

4

3 に答える 3

2

Knuth–Morris–Pratt アルゴリズム

コンピューター サイエンスでは、Knuth-Morris-Pratt 文字列検索アルゴリズム (または KMP アルゴリズム) は、不一致が発生した場合、単語自体が十分な次の一致を開始できる場所を決定するための情報を使用して、以前に一致した文字の再検査をバイパスします。

このアルゴリズムは、1974 年に Donald Knuth と Vaughan Pratt によって考案され、James H. Morris によって独立して考案されました。3人は1977年に共同で出版した。

ウィキペディアから: https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

これは、実行する必要がある改善の 1 つです。小さな違いがあります。コード内の「単語」は、アルゴリズムの用語では「文字」です。あなたの「単語」配列は、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? ...
于 2012-05-08T16:05:24.920 に答える
0

私が行う最初の最適化は、早期失敗です。失敗したことがわかっていても、内部ループはシーケンス全体で継続し、不要なブール論理を実行しています。あなたのコードはこれです：

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

これにより、比較の大部分を節約できます (結果が偽であることがわかっているときに比較を続行するのではなく、一致しない場合は最初の単語でドロップアウトします)。各シーケンス内の個々の単語の出現が少ないと予想される場合 (たとえば、英語のテキストのページで文を見つけている場合)、探している 10 倍の違いが生じる可能性もあります。

于 2012-05-08T11:41:05.433 に答える
0

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

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

return sentences.Count(sentence => sentence.Contains(toMatch));
于 2012-05-08T11:43:48.770 に答える