¿Cómo superar el rendimiento de este reemplazo de regex?

Question

Después de una medición considerable, he identificado un punto de conexión en uno de nuestros servicios de Windows que me gustaría optimizar. Estamos procesando cadenas que pueden tener múltiples espacios consecutivos y nos gustaría reducirlas a espacios únicos. Nosotros usamos una expresión regular compilada estática para esta tarea:

private static readonly Regex 
    regex_select_all_multiple_whitespace_chars = 
     new Regex(@"\s+",RegexOptions.Compiled); 

y luego usamos como sigue:

var cleanString= 
    regex_select_all_multiple_whitespace_chars.Replace(dirtyString.Trim(), " "); 

Esta línea se invoca varios millones de veces, y está demostrando ser bastante intensa. Intenté escribir algo mejor, pero estoy perplejo. Dado los requisitos de procesamiento bastante modestos de la expresión regular, seguramente hay algo más rápido. ¿Podría el proceso unsafe con punteros acelerar las cosas aún más?

Editar:

Gracias por el increíble conjunto de respuestas a esta pregunta ... más inesperado!

Answer 1

Esto es alrededor de tres veces más rápido:

private static string RemoveDuplicateSpaces(string text) { 
    StringBuilder b = new StringBuilder(text.Length); 
    bool space = false; 
    foreach (char c in text) { 
    if (c == ' ') { 
     if (!space) b.Append(c); 
     space = true; 
    } else { 
     b.Append(c); 
     space = false; 
    } 
    } 
    return b.ToString(); 
} 

Answer 2

Sólo una sugerencia, si sus datos no tienen espacios en blanco en lugar de Unicode, \s+ uso [ \r\n]+ o [ \n]+ o simplemente  + (si sólo hay espacio), básicamente se limita al conjunto de caracteres mínimo.

Answer 3

Actualmente, está reemplazando un único espacio con otro espacio único. Intente hacer coincidir \s{2,} (o algo similar, si desea reemplazar las líneas nuevas individuales y otros caracteres).

Answer 4

No se pudieron usar expresiones regulares. Por ejemplo:

private static string NormalizeWhitespace(string test) 
{ 
    string trimmed = test.Trim(); 

    var sb = new StringBuilder(trimmed.Length); 

    int i = 0; 
    while (i < trimmed.Length) 
    { 
     if (trimmed[i] == ' ') 
     { 
      sb.Append(trimmed[i]); 

      do { i++; } while (i < trimmed.Length && trimmed[i] == ' '); 
     } 

     sb.Append(trimmed[i]); 

     i++; 
    } 

    return sb.ToString(); 
} 

Con este método y el siguiente banco de pruebas:

private static readonly Regex MultipleWhitespaceRegex = new Regex(
    @"\s+", 
    RegexOptions.Compiled); 

static void Main(string[] args) 
{ 
    string test = "regex select all multiple  whitespace chars"; 

    const int Iterations = 15000; 

    var sw = new Stopwatch(); 

    sw.Start(); 
    for (int i = 0; i < Iterations; i++) 
    { 
     NormalizeWhitespace(test); 
    } 
    sw.Stop(); 
    Console.WriteLine("{0}ms", sw.ElapsedMilliseconds); 

    sw.Reset(); 

    sw.Start(); 
    for (int i = 0; i < Iterations; i++) 
    { 
     MultipleWhitespaceRegex.Replace(test, " "); 
    } 
    sw.Stop(); 
    Console.WriteLine("{0}ms", sw.ElapsedMilliseconds); 
} 

me dieron los siguientes resultados:

// NormalizeWhitespace - 27ms 
// Regex - 132ms 

Tenga en cuenta que esto sólo se ha probado con un ejemplo muy sencillo , podría optimizarse aún más eliminando la llamada al String.Trim y solo se proporciona para hacer que las expresiones regulares a veces no sean la mejor respuesta.

Answer 5

estoy curioso cómo una aplicación recta hacia adelante podría realizar:

static string RemoveConsecutiveSpaces(string input) 
    { 
     bool whiteSpaceWritten = false; 
     StringBuilder sbOutput = new StringBuilder(input.Length); 

     foreach (Char c in input) 
     { 
      if (c == ' ') 
      { 
       if (!whiteSpaceWritten) 
       { 
        whiteSpaceWritten = true; 
        sbOutput.Append(c); 
       } 
      } 
      else 
      { 
       whiteSpaceWritten = false; 
       sbOutput.Append(c); 
      } 
     } 

     return sbOutput.ToString(); 
    } 

Answer 6

Como se trata de una expresión tan sencilla, en sustitución de dos o más espacios con un solo espacio, deshágase del objeto Regex y codifique el reemplazo usted mismo (en C++/CLI):

String ^text = "Some text to process"; 
bool spaces = false; 
// make the following static and just clear it rather than reallocating it every time 
System::Text::StringBuilder ^output = gcnew System::Text::StringBuilder; 
for (int i = 0, l = text->Length ; i < l ; ++i) 
{ 
    if (spaces) 
    { 
    if (text [i] != ' ') 
    { 
     output->Append (text [i]); 
     spaces = false; 
    } 
    } 
    else 
    { 
    output->Append (text [i]); 
    if (text [i] == ' ') 
    { 
     spaces = true; 
    } 
    } 
} 
text = output->ToString(); 

Answer 7

¿Qué tal esto ...

public string RemoveMultiSpace(string test) 
{ 
var words = test.Split(new char[] { ' ' }, 
    StringSplitOptions.RemoveEmptyEntries); 
return string.Join(" ", words); 
} 

caso de prueba ejecuta con NUnit:
tiempo de prueba es en milisegundos.

Regex Test time: 338,8885 
RemoveMultiSpace Test time: 78,9335 

private static readonly Regex regex_select_all_multiple_whitespace_chars = 
    new Regex(@"\s+", RegexOptions.Compiled); 

[Test] 
public void Test() 
{ 
    string startString = "A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  "; 
    string cleanString; 
    Trace.WriteLine("Regex Test start"); 
    int count = 10000; 
    Stopwatch timer = new Stopwatch(); 
    timer.Start(); 
    for (int i = 0; i < count; i++) 
    { 
     cleanString = regex_select_all_multiple_whitespace_chars.Replace(startString, " "); 
    } 
    var elapsed = timer.Elapsed; 
    Trace.WriteLine("Regex Test end"); 
    Trace.WriteLine("Regex Test time: " + elapsed.TotalMilliseconds); 

    Trace.WriteLine("RemoveMultiSpace Test start"); 
    timer = new Stopwatch(); 
    timer.Start(); 
    for (int i = 0; i < count; i++) 
    { 
     cleanString = RemoveMultiSpace(startString); 
    } 
    elapsed = timer.Elapsed; 
    Trace.WriteLine("RemoveMultiSpace Test end"); 
    Trace.WriteLine("RemoveMultiSpace Test time: " + elapsed.TotalMilliseconds); 
} 

public string RemoveMultiSpace(string test) 
{ 
    var words = test.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); 
    return string.Join(" ", words); 
} 

Editar:
hecho algunas pruebas más y ha añadido Guffa's método "RemoveDuplicateSpaces" basados ​​en StringBuilder.
Así que mi conclusión es que el método StringBuilder es más rápido cuando hay muchos espacios, pero con menos espacios el método de división de cadenas es ligeramente más rápido.

Cleaning file with about 30000 lines, 10 iterations 
RegEx time elapsed: 608,0623 
RemoveMultiSpace time elapsed: 239,2049 
RemoveDuplicateSpaces time elapsed: 307,2044 

Cleaning string, 10000 iterations: 
A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  A B C D E  F  
RegEx time elapsed: 590,3626 
RemoveMultiSpace time elapsed: 159,4547 
RemoveDuplicateSpaces time elapsed: 137,6816 

Cleaning string, 10000 iterations: 
A  B  C  D  E  F  A  B  C  D  E  F  A  B  C  D  E  F  A  B  C  D  E  F  A  B  C  D  E  F  A  B  C  D  E  F  A  B  C  D  E  F  A  B  C  D  E  F  
RegEx time elapsed: 290,5666 
RemoveMultiSpace time elapsed: 64,6776 
RemoveDuplicateSpaces time elapsed: 52,4732 

Answer 8

matrices siempre será más rápido

 public static string RemoveMultiSpace(string input) 
    { 
     var value = input; 

     if (!string.IsNullOrEmpty(input)) 
     { 
      var isSpace = false; 
      var index = 0; 
      var length = input.Length; 
      var tempArray = new char[length]; 
      for (int i = 0; i < length; i++) 
      { 
       var symbol = input[i]; 
       if (symbol == ' ') 
       { 
        if (!isSpace) 
        { 
         tempArray[index++] = symbol; 
        } 
        isSpace = true; 
       } 
       else 
       { 
        tempArray[index++] = symbol; 
        isSpace = false; 
       } 
      } 
      value = new string(tempArray, 0, index); 
     } 

     return value; 
    }