regex - expressions - uso de expresiones regulares

Por qué la expresión regular.*Es más lenta en un lugar y más rápida en otro

Question

Últimamente estoy usando muchas expresiones regulares en java / groovy. Para las pruebas, habitualmente uso regex101.com . Obviamente estoy mirando el rendimiento de expresiones regulares también.

Una cosa que noté es que usar .* Correctamente puede mejorar significativamente el rendimiento general. Principalmente, usar .* En el medio, o mejor dicho para decir que no al final de la expresión regular es el rendimiento.

Por ejemplo, en this expresión regular el número requerido de pasos es 27:

Si cambio primero .* /s* , reducirá los pasos requeridos significativamente a 16:

Sin embargo, si cambio de segundo .* /s* , no se reducen más los pasos:

Tengo algunas preguntas:

1. ¿Por qué lo de arriba? No quiero comparar /s y .* . Yo se la diferencia Quiero saber por qué /s y .* Cuesta diferentes según su posición en la expresión regular completa. Y luego las características de la expresión regular que pueden costar diferentes en función de su posición en la expresión regular (o en función de cualquier otro aspecto distinto de la posición, si existe).
2. ¿El contador de pasos dado en este sitio realmente da alguna indicación sobre el rendimiento de expresiones regulares?
3. ¿Qué otras observaciones de rendimiento de expresiones regulares simples o similares (relacionadas con la posición) tiene?

Answer 1

La forma en que los motores de expresiones regulares funcionan con el cuantificador * , también conocido como cuantificador codicioso , es consumir todo lo que coincida con la entrada, luego:

1. Intenta el siguiente término en la expresión regular. Si coincide, continúa
2. "no consumir" un carácter (mueva el puntero hacia atrás uno), también conocido como retroceder y pasar al paso 1.

Desde coincide con cualquier cosa (casi), el primer estado después del encuentro .* es mover el puntero hasta el final de la entrada, luego comenzar a retroceder a través de la entrada un carácter a la vez, intentando el siguiente término hasta que haya una coincidencia.

Con /s* , solo se consume el espacio en blanco, por lo que el puntero se mueve inicialmente exactamente a donde quiere que esté, no se requiere un retroceso para coincidir con el siguiente término.

Algo que deberías probar es usar el cuantificador renuente .*? , que consumirá una char a la vez hasta que coincida el siguiente término, que debería tener la misma complejidad de tiempo que /s* , pero será un poco más eficiente porque no se requiere una verificación de la char actual.

/s* y .* al final de la expresión se desempeñarán de manera similar, ya que ambos consumirán todo en la entrada final f que coincida, lo que deja al puntero en la misma posición para ambas expresiones.

Answer 2

Lo siguiente es la salida del depurador.

La gran razón de la diferencia en el rendimiento es que .* Consumirá todo hasta el final de la cadena (excepto la nueva línea). El patrón continuará, obligando a la expresión regular a retroceder (como se ve en la primera imagen).

La razón por la cual /s y .* desempeñan igual de bien al final del patrón es que el patrón codicioso frente al espacio en blanco consumidor no hace ninguna diferencia si no hay nada más que coincidir (además de WS).

Si su cadena de prueba no terminara en espacio en blanco, habría una diferencia en el rendimiento, como lo vio en el primer patrón: la expresión regular se vería obligada a retroceder.

EDITAR

Puede ver la diferencia de rendimiento si termina con algo más que espacios en blanco:

Malo:

^myname.*mahesh.*hiworld

Mejor:

^myname.*mahesh/s*hiworld

Aun mejor:

^myname/s*mahesh/s*hiworld