大文字と小文字を区別しないasciiサブ文字列を効率的に検索

Question

私は実際に大きな文字列のRegex変換を最適化していました。 Regex.Replaceにはいくつかの呼び出しは、私は条件付きの呼び出しを挿入し、かなりの時間を要したとして - 線に沿って何か

if (str.IndexOf("abc", 0, StringComparison.CurrentCultureIgnoreCase) > 0) 
    str1 = Regex.Replace(str, "abc...", string.Empty, RegexOptions.IgnoreCase); 

を驚いたことに結果は説得力がありませんでした。ときには良い、時にはない。またはさらに悪い。だから私は、大文字小文字を区別しないIndexOfメソッドのパフォーマンスを（私もStringComparison.OrdinalIgnoreCaseを試してみました）を測定し、それがこのテストすなわち、Regex.Matchよりも遅くなることが分かっ：特に一致しませんでした大きな文字列のための

if(Regex.Match(str,"abc", RegexOptions.IgnoreCase).Success)... 

（アスキー）string "abc" Regex.Matchが4倍速かったことがわかりました。

であっても、この手順では、IndexOfメソッドよりも高速です：

string s1 = str.ToLower(); 
if(s1.IndexOf("abc")) ... 

誰もがよりよい解決策を知っていますか？

Answer 1

indexOfはO（n * m）ですので、RegExはO（n + m）（ここでn =文字列長、m =検索文字列長）となります。

あなたが深刻なアブストラクトの部分文字列を検索している場合は、少なくとも文字列検索アルゴリズムを読んで、予想される速度を少なくとも知っておくと便利です（http://en.wikipedia.org/wiki/Substring_searchで始まる）。

注：文化的感受性の比較は、標準よりも大幅に遅くなることがあります（シナリオによっては、序数バージョンを使用できない場合があります）。

パフォーマンスに関する質問と同様に、測定して測定する必要があります。 Regex.isMatchのindexOfでは、私にとって明らかな勝者はRegexです。私はindexOfが検索文字列のプリコンパイルを実行してはならず、O（n + m）アルゴリズムを使用しなければならないと予想しましたが、Regexはもっと最適な実装を使用しなければなりません。

次の検索を行うことをお勧めします - 私はRegexに100K操作のためにほぼ5倍の違いがあります。

static void Main(string[] args) 
    { 
     var stringToSearch = "AAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAAbb"; 
     Regex regExp = new Regex(stringToSearch, RegexOptions.Compiled | RegexOptions.CultureInvariant | RegexOptions.IgnoreCase); 

     var sourceText = "AAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAAbb"; 

     const int Iterations = 100000; 

     Stopwatch watch = new Stopwatch(); 
     watch.Start(); 
     for (int i = 0; i < Iterations; i++) 
     { 
      regExp.IsMatch(sourceText); 
     } 
     watch.Stop(); 
     Console.WriteLine("RegExp: {0} ms", watch.ElapsedMilliseconds); 

     watch = new Stopwatch(); 
     watch.Start(); 
     for (int i = 0; i < Iterations; i++) 
     { 
      sourceText.IndexOf(stringToSearch, StringComparison.OrdinalIgnoreCase); 
     } 
     watch.Stop(); 
     Console.WriteLine("RegExp: {0} ms", watch.ElapsedMilliseconds); 
     Console.ReadLine(); 
    } 

Answer 2

最終的に私はマッチテストのために私自身の機能を書いた。これは次のとおりです。

private static bool HasAsciiSubstring(string str, string sub) 
{ 
    char[] ss = sub.ToCharArray(); 

    // Similar stupid small optimizations bring 30% speeding-up. 
    int ss_len = ss.Length; 
    for (int j = 0; j < ss_len; ++j) 
     ss[j] = (char)((byte)ss[j] | 32); 

    byte ss0 = (byte)ss[0]; 
    int len = str.Length - ss_len; 
    for (int i = 0; i < len; ++i) 
    { 
     if ((str[i] | 32) == ss0) 
     { 
      bool bOk = true; 
      for (int j = 1; j < ss_len; ++j) 
      { 
       if ((str[i + j] | 32) != ss[j]) 
       { 
        bOk = false; 
        break; 
       } 
      } 
      if (bOk) 
       return true; 
     } 
    } 

    return false; 
} 

この方法は、WP7プラットフォームで（選択した大きな文字列に対して）最良の結果をもたらしました。これはRegex.Match（STR、サブ、RegexOptions.IgnoreCase）

おおよそ10倍str.IndexOfよりも速く（サブ、0、StringComparison.CurrentCultureIgnoreCase）

str.IndexOf（サブより

• 2倍速かったです、0、StringComparison.OrdinalIgnoreCase）は、CurrentCultureIgnoreCaseより30％遅かった。

私は、WP7、MonoDroid/Touch、そして恐らくデスクトップ上ではうまくいくでしょう。したがって、少なくともデスクトップをテストするための小さなWPFアプリケーションを作成しました：

• Regex.Match（）はHasAsciiSubstring（）よりも2倍高速です。
• OrdinalIgnoreCase 2。5倍遅く
• CurrentCultureIgnoreCase
より残りの部分は同様の

である私は、C＃の/。ネット（のみ2年以上の経験）に比較的新しいですが、他のプラットフォーム（主にC/C++）に数十年をプログラムします。

• 非効率的なC＃の文字列関数
• 非効率的なC＃の言語をツールとして：私は私のために、これは衝撃的な体験のようなものだったことをダウンさせる必要があります。 （私は、C++で書かれた同じコードがはるかに優れていると確信しています）
• この複雑な文化ビジネスと、CurrentCultureIgnoreCaseがOrdinalIgnoreCaseよりもはるかに優れていたという事実。 （私の周りの経験豊富なC＃プログラマのように見えますが）逆さまです。