6

大きなテキストファイル（300〜600 MB）で文字列の検索を最適化しようとしています。私の現在の方法を使用すると、時間がかかりすぎます。

現在IndexOf、文字列の検索に使用していますが、文字列を使用して各行のインデックスを作成するには時間がかかりすぎます（20秒）。

検索速度を最適化するにはどうすればよいですか？私は試しましContains()たが、それも遅いです。助言がありますか？正規表現の一致を考えていましたが、大幅な速度の向上は見られません。たぶん私の検索ロジックに欠陥があります

例

while ((line = myStream.ReadLine()) != null)
{
    if (line.IndexOf(CompareString, StringComparison.OrdinalIgnoreCase) >= 0)
    {
        LineIndex.Add(CurrentPosition);
        LinesCounted += 1;
    }
}
4

4 に答える 4

12

使用しているブルート フォース アルゴリズムは、O(nm)時間で実行されます。ここで、nは検索される文字列の長さであり、mは検索しようとしている部分文字列/パターンの長さです。文字列検索アルゴリズムを使用する必要があります:

ただし、探しているものによっては、慎重に作成された正規表現を使用するだけで十分な場合があります。Jeffrey の Friedl の著書Mastering Regular Expressionsを参照して、効率的な正規表現を作成する方法を確認してください (たとえば、バックトラックなし)。

また、優れたアルゴリズムのテキストを参照することもできます。私はRobert SedgewickのAlgorithmsのさまざまな化身（[C | C ++ | Java]のアルゴリズム）に部分的です

于 2012-12-19T19:23:38.427 に答える
2

残念ながら、ストレートな C# でできることはそれほど多くないと思います。

Boyer-Moore アルゴリズムは、このタスクに対して非常に高速であることがわかりました。しかし、それを .500 秒ほど速くする方法はないことがわかりましたIndexOf。IndexOfこれは、私のコードが C# で実行されている間に、手作業で最適化されたアセンブラーで実装されているためだと思います。

私のコードとパフォーマンス テストの結果は、Fast Text Search with Boyer-Mooreという記事で確認できます。

于 2012-12-19T19:42:03.420 に答える
1

これらの質問 (および回答) を見たことがありますか?

テキストファイルを読むことだけが目的なら、今のやり方が良いようです。その他のアイデア:

  • テキスト ファイルに挿入するときなど、データを事前に並べ替えることができれば、それが役立つ可能性があります。

  • データをデータベースに挿入し、必要に応じてクエリを実行できます。

  • ハッシュテーブルを使用できます

于 2012-12-19T19:15:28.307 に答える
1

regexp.Match(String) を使用できます。RegExp Match の方が高速です。

static void Main()

{

  string text = "One car red car blue car";
  string pat = @"(\w+)\s+(car)";

  // Instantiate the regular expression object.
  Regex r = new Regex(pat, RegexOptions.IgnoreCase);

  // Match the regular expression pattern against a text string.
  Match m = r.Match(text);
  int matchCount = 0;
  while (m.Success) 
  {
     Console.WriteLine("Match"+ (++matchCount));
     for (int i = 1; i <= 2; i++) 
     {
        Group g = m.Groups[i];
        Console.WriteLine("Group"+i+"='" + g + "'");
        CaptureCollection cc = g.Captures;
        for (int j = 0; j < cc.Count; j++) 
        {
           Capture c = cc[j];
           System.Console.WriteLine("Capture"+j+"='" + c + "', Position="+c.Index);
        }
     }
     m = m.NextMatch();
  }

}

于 2012-12-19T19:26:57.097 に答える