Inverse String.Replace - それをより速く行う方法？

Question

私は指定した文字以外のすべての文字を置き換える方法があります。例えば、

ReplaceNot("test. stop; or, not", ".;/\\".ToCharArray(), '*'); 

は今

 
"****.*****;***,****". 

を返します、これは時期尚早の最適化のインスタンスではありません。私はネットワーク操作中にこのメソッドをかなり数回呼び出します。長い文字列では待ち時間があり、それを取り除くと少し助けになることがわかった。これをスピードアップするための助けをいただければ幸いです。

public static string ReplaceNot(this string original, char[] pattern, char replacement) 
    {   
     int index = 0; 
     int old = -1; 

     StringBuilder sb = new StringBuilder(original.Length); 

     while ((index = original.IndexOfAny(pattern, index)) > -1) 
     { 
      sb.Append(new string(replacement, index - old - 1)); 
      sb.Append(original[index]); 
      old = index++; 
     } 

     if (original.Length - old > 1) 
     { 
      sb.Append(new string(replacement, original.Length - (old + 1))); 
     } 

     return sb.ToString(); 
    } 

ファイナル＃ 's。また、3Kの文字列のテストケースを追加し、1Mの代わりに100K回実行して、これらのスケールのそれぞれがどれほど優れているかを確認しました。唯一の驚きは、正規表現が他のものより「より良いスケール」ということでしたが、そもそも非常に遅いので、それは何の助けではありません：

 
User   Short * 1M Long * 100K  Scale 
John   319    2125   6.66 
Luke   360    2659   7.39 
Guffa   409    2827   6.91 
Mine   447    3372   7.54 
DirkGently  1094   9134   8.35 
Michael   1591   12785   8.04 
Peter   21106   94386   4.47 

アップデート：私はピーターのバージョンの正規表現の作成を行いました静的変数、かつ公正であることをRegexOptions.Compiledに設定します。

 
User   Short * 1M  Long * 100K  Scale 
Peter   8997   74715   8.30 

私のテストコードに

ペーストビンリンクそれが間違っている場合、私を修正してください： http://pastebin.com/f64f260ee

Answer 1

さてさて、〜60キロバイトの文字列で、これはあなたのバージョンより約40％速く実行します。

public static string ReplaceNot(this string original, char[] pattern, char replacement) 
{ 
    int index = 0; 

    StringBuilder sb = new StringBuilder(new string(replacement, original.Length)); 

    while ((index = original.IndexOfAny(pattern, index)) > -1) 
    { 
     sb[index] = original[index++]; 
    } 

    return sb.ToString(); 
} 

トリックほとんどの文字が置換されるため、すべての置換文字で新しい文字列を初期化することです。

これはどの速くなりますが、それが役立つ可能性がある、彼らは文字列ビルダに追加できるだけのでNEWINGまでの文字列を回避した場合、私は知らない

Answer 2

それはO（になるだろうn）。あなたはすべてのアルファベットと空白を*で置き換えているようですが、現在の文字がアルファベット/空白であるかどうかテストして置き換えてみませんか？

Answer 3

あなたがそうのようなRegex.Replaceを使用することはできません：

Regex regex = new Regex(@"[^.;/\\]"); 
string s = regex.Replace("test. stop; or, not", "*"); 

Answer 4

：

public static string ReplaceNot(this string original, char[] pattern, char replacement) 
    { 
     StringBuilder sb = new StringBuilder(original.Length); 

     foreach (char ch in original) { 
      if (Array.IndexOf(pattern, ch) >= 0) { 
       sb.Append(ch); 
      } 
      else { 
       sb.Append(replacement); 
      } 
     } 

     return sb.ToString(); 
    } 

中の文字数場合patternはどんなサイズでも構いませんが（私はそれが一般的にはそうではないと推測しています）、それをソートして、Array.indexOf()の代わりにArray.BinarySearch()を実行します。

このような単純な変換では、正規表現よりも高速で問題がないと確信しています。

：あなたはメソッドのシグネチャがあることはありません、なぜまた

、pattern内の文字のあなたのセットは、通常、（少なくとも、それはAPIのこのタイプの私の一般的な経験をされている）とにかく文字列から来る可能性があることから、

以上で、patternがchar[]またはstringになる可能性があります。

Answer 5

StringBuilderには文字とカウントが必要なオーバーロードがあるため、StringBuilderに追加する中間文字列を作成する必要はありません。

sb.Append(new string(replacement, original.Length - (old + 1))); 

：で

sb.Append(new string(replacement, index - old - 1)); 

：

sb.Append(replacement, index - old - 1); 

この私はこれを置き換えることによって、約20％の改善を得る

sb.Append(replacement, original.Length - (old + 1)); 

（Iコードをテストあなたが言ったことは約4倍速かったと私はそれを見つける約15倍遅く...）

Answer 6

ここで別のバージョンがあります。私のテストは、その性能がかなり良いと示唆しています。

public static string ReplaceNot(
    this string original, char[] pattern, char replacement) 
{ 
    char[] buffer = new char[original.Length]; 

    for (int i = 0; i < buffer.Length; i++) 
    { 
     bool replace = true; 

     for (int j = 0; j < pattern.Length; j++) 
     { 
      if (original[i] == pattern[j]) 
      { 
       replace = false; 
       break; 
      } 
     } 

     buffer[i] = replace ? replacement : original[i]; 
    } 

    return new string(buffer); 
}