Inverse String.Replace - Schneller geht es?

Question

Ich habe eine Methode, um jedes Zeichen außer den angegebenen zu ersetzen. Zum Beispiel

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

zurückkehren würden

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

Nun, dies ist nicht eine Instanz vorzeitiger Optimierung ist. Ich rufe diese Methode während einer Netzwerkoperation einige Male auf. Ich habe festgestellt, dass es bei längeren Saiten etwas Latenz verursacht, und das Entfernen hat etwas geholfen. Jede Hilfe, um dies zu beschleunigen, wäre willkommen.

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

Endgültige # s. Ich fügte auch einen Testfall für eine 3K Zeichenkette hinzu, lief bei 100K mal anstelle von 1M, um zu sehen, wie gut jede dieser Skalen ist. Die einzige Überraschung war, dass der reguläre Ausdruck ‚besser skaliert‘ als die anderen, aber es ist keine Hilfe, da es sehr langsam beginnen:

 
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 

Update: Ich habe die Schaffung des regulären Ausdrucks für Peters Version eine statische Variable, und es RegexOptions.Compiled gesetzt, fair zu sein:

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

Pastebin Link zu meinem Test-Code, bitte korrigieren sie mich, wenn es falsch ist: http://pastebin.com/f64f260ee

Answer 1

Ordnung, auf einem ~ 60KB String, wird dies etwa 40% schneller als die Version ausführen besteht darin, eine neue Zeichenfolge mit allen Ersatzzeichen zu initialisieren, da die meisten davon ersetzt werden.

Answer 2

es O sein wird (n). Sie scheinen alle Alphabete und Leerzeichen durch * zu ersetzen, warum testen Sie nicht einfach, ob das aktuelle Zeichen ein Alphabet/Leerzeichen ist und ersetzen Sie es?

Answer 3

Können Sie nicht verwenden Regex.Replace wie so:

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

Der Trick:

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

Answer 4

Ich weiß nicht, ob dies schneller sein wird, aber es vermeidet Saiten newing bis nur so können sie auf den String-Builder angehängt werden können, die helfen können:

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

Wenn die Anzahl der Zeichen in pattern wird von jeder Größe sein (die ich vermute es wird in der Regel nicht), könnte es sich auszahlen, es zu sortieren und eine Array.BinarySearch() anstelle der Array.indexOf() durchzuführen.

Für solch eine einfache Umwandlung würde ich wetten, dass es kein Problem haben wird, schneller als eine Regex auch zu sein.

Da auch Ihren Satz von Zeichen in pattern wahrscheinlich ist in der Regel aus einem String trotzdem kommen (zumindest das ist schon meine allgemeine Erfahrung mit dieser Art von API), warum Sie nicht die Methode Signatur sein:

public static string ReplaceNot(this string original, string pattern, char replacement) 

oder noch besser, haben eine Überlastung wo pattern ein char[] oder string sein kann?

Answer 5

Der StringBuilder hat eine Überladung, die ein Zeichen und eine Anzahl akzeptiert, so dass Sie keine Zwischenzeichenfolgen zum Hinzufügen zum StringBuilder erstellen müssen. Ich bekomme etwa 20% ige Verbesserung durch diese ersetzt:

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

mit:

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

und diese:

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

mit:

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

(Getestet habe ich den Code das du gesagt hast war ungefähr viermal schneller, und ich finde es etwa 15 mal langsamer ...)

Answer 6

Hier ist eine andere Version für Sie. Meine Tests deuten darauf hin, dass seine Leistung ziemlich gut ist.

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