Inverse String.Replace - ¿Forma más rápida de hacerlo?

Question

Tengo un método para reemplazar todos los caracteres excepto los que especifico. Por ejemplo,

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

regresarían

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

Ahora, esto no es una instancia de la optimización prematura. Llamo a este método varias veces durante una operación de red. Descubrí que en cadenas más largas, está causando cierta latencia, y eliminarlo ayudó un poco. Cualquier ayuda para acelerar esto sería apreciada.

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

Final # 's. También agregué un caso de prueba para una cadena de caracteres de 3K, ejecuté 100K veces en vez de 1M para ver qué tan bien cada una de estas escalas. La única sorpresa fue que la expresión regular 'escaló mejor' que los otros, pero no es de ayuda, ya que es muy lento para empezar:

 
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 

actualización: Hice la creación de la expresión regular para la versión de Peter una variable estática, y la puso a RegexOptions.Compiled para ser justos:

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

Pastebin enlace a mi código de prueba, por favor, corríjanme si está mal: http://pastebin.com/f64f260ee

Answer 1

bien, en una cadena ~ 60 KB, esto llevará a cabo alrededor del 40% más rápido que su versión:

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

El truco es inicializar una nueva cadena con todos los caracteres de reemplazo, ya que la mayoría de ellos serán reemplazados.

Answer 2

que va a ser O (norte). Parece que está reemplazando todos los alfabetos y espacios en blanco por *, ¿por qué no simplemente prueba si el carácter actual es un alfabeto/espacio en blanco y lo reemplaza?

Answer 3

No se puede utilizar Regex.Replace así:

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

Answer 4

No sé si esto va a ser más rápido, pero evita Newing hasta cuerdas sólo para que puedan ser adjuntados a la constructor de cadena, que pueden ayudar:

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

Si el número de caracteres en pattern será de cualquier tamaño (que supongo que generalmente no), podría ser útil ordenarlo y realizar un Array.BinarySearch() en lugar del Array.indexOf().

Para una transformación tan simple, apostaría a que no tendrá problema en ser más rápido que una expresión regular, también.

Además, dado que el conjunto de caracteres en pattern es probable que lleguen por lo general de una cadena de todos modos (al menos esa ha sido mi experiencia en general con este tipo de API), ¿por qué no tienen la firma del método es:

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

o mejor aún, tener una sobrecarga en pattern puede ser un char[] o string?

Answer 5

StringBuilder tiene una sobrecarga que toma un carácter y un recuento, por lo que no tiene que crear cadenas intermedias para agregar a StringBuilder. Consigo una mejora de aproximadamente 20% mediante la sustitución de esto:

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

con:

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

y esto:

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

con:

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

(He probado el código que dijiste era aproximadamente cuatro veces más rápido, y lo encontré aproximadamente 15 veces más lento ...)

Answer 6

Aquí hay otra versión para usted. Mis pruebas sugieren que su rendimiento es bastante bueno.

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