Regex lento rendimiento

Question

El siguiente código contiene una expresión regular diseñada para extraer un literal de cadena C#, pero el rendimiento de la expresión regular para cadenas de entrada de más de unos pocos caracteres es lamentable.

class Program 
{ 
    private static void StringMatch(string s) 
    { 
     // regex: quote, zero-or-more-(zero-or-more-non-backslash-quote, optional-backslash-anychar), quote 
     Match m = Regex.Match(s, "\"(([^\\\\\"]*)(\\\\.)?)*\""); 
     if (m.Success) 
      Trace.WriteLine(m.Value); 
     else 
      Trace.WriteLine("no match"); 
    } 

    public static void Main() 
    { 
     // this first string is unterminated (so the match fails), but it returns instantly 
     StringMatch("\"OK"); 

     // this string is terminated (the match succeeds) 
     StringMatch("\"This is a longer terminated string - it matches and returns instantly\""); 

     // this string is unterminated (so the match will fail), but it never returns 
     StringMatch("\"This is another unterminated string and takes FOREVER to match"); 
    } 
} 

puedo refactorizar la expresión regular en una forma diferente, pero cualquier persona puede ofrecer una explicación de por qué el rendimiento es tan malo?

Answer 1

usted está funcionando en catastrophic backtracking:

vamos a simplificar la expresión regular un poco (sin las comillas escapado y sin el segundo grupo opcional, ya que, al igual que en su comentario, es irrelevante para las cadenas analizadas):

"(([^\\"]*))*" 

([^\\"]*) coincide con cualquier cadena excepto las comillas o las barras diagonales inversas. Este nuevamente está encerrado en un grupo opcional que puede repetirse cualquier cantidad de veces.

Ahora para la cadena "ABC, el motor de expresiones regulares hay que tratar las siguientes permutaciones:

• ", ABC
• ", ABC, <empty string>
• ", AB, C
• ", AB, C, <empty string>
• ", AB, <empty string>, C
• ", AB, <empty string>, C, <empty string>
• ", <empty string>, AB, C
• ", <empty string>, AB, C, <empty string>
• ", <empty string>, AB, <empty string>, C, <empty string>
• ", <empty string>, AB, <empty string>, C
• ", A, BC
• ", A, BC, <empty string>
• ", A, <empty string> , BC
• ", <empty string>, A, BC
• etc.
• ", A, B, C
• ", A, B, C, <empty string>
• ", A, B, <empty string>, C
• etc. etc.

cada uno de los cuales luego falla porque no hay followi ng ".

Además, solo está probando subcadenas en lugar de forzar a la expresión regular para que coincida con toda la cadena. Y generalmente quiere usar cadenas verbales para expresiones regulares para reducir el número de barras diagonales inversas que necesita. ¿Qué tal esto:

foundMatch = Regex.IsMatch(subjectString, 
    @"\A  # Start of the string 
    ""  # Match a quote 
    (?:  # Either match... 
    \\.  # an escaped character 
    |  # or 
    [^\\""] # any character except backslash or quote 
    )*  # any number of times 
    ""  # Match a quote 
    \Z  # End of the string", 
    RegexOptions.IgnorePatternWhitespace); 

Answer 2

Trate

Match m = Regex.Match(s, @"'.*?(?<=[^\\](\\\\)*)'".Replace("'", "\"")); 

Esta será "inteligente" ignorar un número par de \. Esto porque " cierra una cadena, \" no lo hace, lo hace \\" (porque la primera barra invertida se escapa el segundo), \\\" no lo hace ...

.*? es un cuantificador perezoso. Incluso puede usar el cuantificador estándar .*. Diré que quizás deberías anclar tu expresión regular con ^ y $.

estoy usando el Reemplazar porque escapan comillas dobles me dio dolores de cabeza :-)

voy a añadir que con un texto 4k es instantáneo en mi equipo, tanto en el partido y no coinciden.

Como alternativa:

Match m = Regex.Match(s, @"^'(?>([^'\\]|\\.)*)'$".Replace("'", "\"")); 

Explicación:

(?>) disables backtracking 

^ begin of the string 

entonces usted tiene una construcción alterna (0 o más veces, el *):

[^'\\] any non-quote and non backslash 

\\. or a backslash followed by another character (that is escaped) 

$ end of the string 

Esto también es muy, muy rápido, y es bastante fácil de leer.

Answer 3

EDITAR

Aquí van: "\"([^\\\\\"]|\\\\.)*\""

de explicar, después de C# se ha escapado de la cadena que recibe esta expresión regular: "([^\\"]|\\.)*"

Significado:

"    #start with a quote 
(
    [^\\"]  #match a non backslash or quote 
    |   #or 
    \\.   #backslash something 
)     
*    #And repeat 
"    #end with a quote 

Por no anidando tu * no obtienes el expone ciclo inicial o infinito, y vuelve instantáneamente para mí.

Answer 4

Creo que @Tim Pietzcker dio la mejor explicación sobre el retroceso.

A través de varios puntos de referencia en torno (el mío incluido) éstas son las formas rápidas:

Método 1, desenrollando

" [^"\\]* (?: \\. [^"\\]*)* " 

Método 2, la alternancia

" (?: \\. | [^"\\]+)* " 

Método 1, puede superar 2 por márgenes sustanciales.

información

Creo que es muy difícil de explicar el retroceso catastrófico. Incluso reconocerlo a veces es difícil a menos que sea muy evidente en el tiempo. Luego, en aplicaciones de tiempo crítico, a veces es beneficioso hacer algunos puntos de referencia.

En este tema de citas, me gusta agregar nuevos enfoques a una secuencia de comandos de perl templada de referencia (5.10) para ver cómo funciona. Cada motor es un poco diferente. Si te importa, aquí hay una muestra.

muestras Regex en función del tiempo utilizando una cadena pesada y entre comillas
iterada 100.000 veces cada una.

(?x-ism:" ((?: \\?.)*?) ")
el código tomó: 14.7031 secs wallclock (14.58 usr + 0.00 sys = 14,58 CPU)

(?x-ism:" (.*? (?<!\\) (?:\\{2})*) ")
el código tomó: 12.8435 secs wallclock (12,75 usr + 0.00 sys = 12,75 CPU)

(?x-ism:" ((?: [^\\"] | \\.)*) ")
el código tomó: 10.3123 segundos wallclock (10.27 usr + 0.00 = 10.27 sys CPU)

(?x-ism: " ((?: [^"\\]+ | (?:\\.)+)*) ")
el código tomó: 8.39063 secs wallclock (8.39 usr + 0.00 sys = 8,39 CPU)

(?x-ism: " ((?: [^"\\]+ | \\.)*) ")
el código tomó: 8.7498 secs wallclock (8,75 usr + 0.00 sys = 8,75 CPU)

(?x-ism: " ((?: \\. | [^"\\]+)*) ")
el código tomó: 8.5623 secs wallclock (8.44 usr + 0.00 sys = 8,44 CPU)

(?x-ism: " ([^"\\]* (?: \\. [^"\\]*)*) ")
el código tomó: 7.79661 secs wallclock (7,80 usr + 0.00 sys = 7,80 CPU)

(?x-ism: (?> " ((?: [^"\\] | \\.)* ")))
el código tomó: 10.5156 segundos wallclock (10,52 usr + 0.00 = 10.52 sys CPU)

Answer 5

Esto es lo que yo usaría:

"[^\n"\\]*(?:\\.[^\n"\\]*)*" 

@sln es correcta sobre la unrolled- el enfoque de bucle es el más rápido, pero lo refinaría un poco más al excluir saltos de línea, que no están permitidos en los literales de cadena pasados ​​de moda.La pieza \\. está bien, pero [^"\\] debe cambiarse a [^\n"\\]. Además, si estamos hablando de extrayendo literales de cadena, no podemos anclar la expresión regular con \A y \Z.

Utilicé RegexBuddy para comparar el rendimiento de su expresión regular, la expresión regular de Tim sin los anclajes, y este. Coloqué el cursor antes de la cita de apertura en cada una de sus cadenas de muestra y se utiliza "depuración Aquí", y estos son los resultados:

original regex  : "(([^\\"\n]*)(\\.)?)*" 

"OK     : failed in 101 steps 

"This is a longer... : matched in 12 steps 

"This is another... : gave up after 1,000,000 steps 



Tim's regex   : "(?:\\.|[^\\"\n])*" 

"OK     : failed in 17 steps 

"This is a longer... : matched in 211 steps 

"This is another... : failed in 253 steps 


unrolled loop   : "[^\\"\n]*(?:\\.[^\\"\n]*)*" 

"OK     : failed in 5 steps 

"This is a longer... : matched in 5 steps 

"This is another... : failed in 5 steps 

Taponamiento que en su código como una cadena pie de la letra, se llega a:

Match m = Regex.Match(s, @"""[^\n""\\]*(?:\\.[^\n""\\]*)*"""); 

EDIT: Por cierto, no estoy diciendo que imprescindible el uso de expresiones regulares esto porque es más rápido; las otras soluciones son casi con toda seguridad lo suficientemente rápidas. Pero si necesitas el máximo rendimiento (mientras usas regex), esta es probablemente la forma de lograrlo. Lo que lo hace tan rápido es que la expresión regular siempre se mueve hacia adelante: sin retroreferencias, sin previsualizaciones, y lo más importante, sin retrocesos.