validate tester regular online one creator regex perl regex-greedy

regex - tester - ¿Por qué es `/ s+` mucho más rápido que `/ s / s*` en esta expresión regular de Perl?



regular expression creator online (4)

¿Por qué reemplazar /s* (o incluso /s/s* ) con /s+ resultado una aceleración de esta entrada?

use Benchmark qw(:all); $x=(" " x 100000) . "_/n"; $count = 100; timethese($count, { ''//s/s*/n/'' => sub { $x =~ //s/s*/n/ }, ''//s+/n/'' => sub { $x =~ //s+/n/ }, });

Enlace a la versión en línea

Noté una expresión regular lenta s//s*/n/s*//n/g en mi código, cuando recibí un archivo de entrada de 450 KB que consta de muchos espacios con algunos no espacios aquí y allá, y una nueva línea final en Al final, la expresión regular colgó y nunca terminó.

Intuitivamente reemplacé la expresión regular con s//s+/n//n/g; s//n/s+//n/g; s//s+/n//n/g; s//n/s+//n/g; y todo estuvo bien.

¿Pero por qué es mucho más rápido? Después de usar re Debug => "EXECUTE" , noté que la versión /s+ alguna manera está optimizada para ejecutarse en una sola iteración: http://pastebin.com/0Ug6xPiQ

Matching REx "/s*/n" against " _%n" Matching stclass ANYOF{i}[/x09/x0a/x0c/x0d ][{non-utf8-latin1-all}{unicode_all}] against " _%n" (9 bytes) 0 <> < _%n> | 1:STAR(3) SPACE can match 7 times out of 2147483647... failed... 1 < > < _%n> | 1:STAR(3) SPACE can match 6 times out of 2147483647... failed... 2 < > < _%n> | 1:STAR(3) SPACE can match 5 times out of 2147483647... failed... 3 < > < _%n> | 1:STAR(3) SPACE can match 4 times out of 2147483647... failed... 4 < > < _%n> | 1:STAR(3) SPACE can match 3 times out of 2147483647... failed... 5 < > < _%n> | 1:STAR(3) SPACE can match 2 times out of 2147483647... failed... 6 < > < _%n> | 1:STAR(3) SPACE can match 1 times out of 2147483647... failed... 8 < _> <%n> | 1:STAR(3) SPACE can match 1 times out of 2147483647... 8 < _> <%n> | 3: EXACT </n>(5) 9 < _%n> <> | 5: END(0) Match successful!

Matching REx "/s+/n" against " _%n" Matching stclass SPACE against " _" (8 bytes) 0 <> < _%n> | 1:PLUS(3) SPACE can match 7 times out of 2147483647... failed...

Sé que Perl 5.10+ fallará inmediatamente la expresión regular (sin ejecutarla) si no hay una nueva línea. Sospecho que está utilizando la ubicación de la nueva línea para reducir la cantidad de búsquedas que realiza. Para todos los casos anteriores, parece reducir inteligentemente el retroceso involucrado (generalmente //s*/n/ contra una cadena de espacios tomaría un tiempo exponencial). ¿Alguien puede ofrecer una idea de por qué la versión /s+ es mucho más rápida?

También tenga en cuenta que /s*? No ofrece ninguna aceleración.

Cuando hay un nodo "más" (por ejemplo, /s+ ) al comienzo de un patrón y el nodo no coincide, el motor de expresiones regulares salta al punto de falla e intenta nuevamente; con /s* , por otro lado, el motor solo avanza un personaje a la vez.

Yves Orton explica esta optimización muy bien here :

La optimización de la clase de inicio tiene dos modos, "prueba cada posición de inicio válida" (doevery) y "modo flip flop" (! Doevery) donde intenta solo la primera posición de inicio válida en una secuencia.

Considere / (/ d +) X / y la cadena "123456Y", ahora sabemos que si no podemos hacer coincidir X después de hacer coincidir "123456", entonces también fallaremos después de "23456" (suponiendo que no haya trucos malvados, que deshabilita la optimización de todos modos), por lo que sabemos que podemos avanzar hasta la comprobación / falla / y solo entonces comenzar a buscar una coincidencia real. Este es el modo flip-flop.

//s+/ activa el modo flip-flop; //s*/ , //s/s*/ , y //s/s+/ don''t. Esta optimización no se puede aplicar a los nodos "estrella" como /s* porque pueden coincidir con cero caracteres, por lo que una falla en un punto de una secuencia no es indicativa de falla más adelante en la misma secuencia.

Puede ver esto en la salida de depuración para cada expresión regular. He resaltado los caracteres omitidos con ^ . Compare esto (omite cuatro caracteres a la vez):

$ perl -Mre=Debug,MATCH -e''"123 456 789 x" =~ //d+x/'' ... 0 <> <123 456 78> | 1:PLUS(3) POSIXD[/d] can match 3 times out of 2147483647... failed... 4 <123 > <456 789 x> | 1:PLUS(3) ^^^^ POSIXD[/d] can match 3 times out of 2147483647... failed... 8 <23 456 > <789 x> | 1:PLUS(3) ^^^^ POSIXD[/d] can match 3 times out of 2147483647... failed...

a esto (omite uno o dos caracteres a la vez):

$ perl -Mre=Debug,MATCH -e''"123 456 789 x" =~ //d*x/'' ... 0 <> <123 456 78> | 1:STAR(3) POSIXD[/d] can match 3 times out of 2147483647... failed... 1 <1> <23 456 789> | 1:STAR(3) ^ POSIXD[/d] can match 2 times out of 2147483647... failed... 2 <12> <3 456 789 > | 1:STAR(3) ^ POSIXD[/d] can match 1 times out of 2147483647... failed... 4 <123 > <456 789 x> | 1:STAR(3) ^^ POSIXD[/d] can match 3 times out of 2147483647... failed... 5 <123 4> <56 789 x> | 1:STAR(3) ^ POSIXD[/d] can match 2 times out of 2147483647... failed... 6 <23 45> <6 789 x> | 1:STAR(3) ^ POSIXD[/d] can match 1 times out of 2147483647... failed... 8 <23 456 > <789 x> | 1:STAR(3) ^^ POSIXD[/d] can match 3 times out of 2147483647... failed... 9 <23 456 7> <89 x> | 1:STAR(3) ^ POSIXD[/d] can match 2 times out of 2147483647... failed... 10 <23 456 78> <9 x> | 1:STAR(3) ^ POSIXD[/d] can match 1 times out of 2147483647... failed... 12 <23 456 789 > <x> | 1:STAR(3) ^^ POSIXD[/d] can match 0 times out of 2147483647... 12 <23 456 789 > <x> | 3: EXACT <x>(5) 13 <23 456 789 x> <> | 5: END(0)

Tenga en cuenta que la optimización no se aplica a //s/s+/ , porque /s+ no está al comienzo del patrón. Sin embargo, tanto //s/s+/ (lógicamente equivalente a //s{2,}/ ) como //s/s*/ (lógicamente equivalente a //s+/ ) probablemente podrían optimizarse; podría tener sentido preguntar a perl5-porters si valdría la pena el esfuerzo.

En caso de que esté interesado, el "modo flip-flop" se habilita configurando el indicador PREGf_SKIP en una expresión regular cuando se compila. Vea el código alrededor de las líneas 7344 y 7405 en regcomp.c y la línea 1585 en regexec.c en la fuente 5.24.0.

El /s+/n requiere que el carácter que precede al /n sea ​​un SPACE .

Según el use re qw(debug) la compilación establece que necesita una cadena recta de un número conocido de espacios, hasta la subcadena /n , que primero se verifica en la entrada. Luego comprueba la subcadena de espacio fijo de longitud fija con la parte restante de la entrada, fallando en lo que respecta a _ . Es una posibilidad única de verificar, independientemente de cuántos espacios tenga la entrada. (Cuando hay más _/n cada uno falla igualmente de forma directa, por salida de depuración).

Visto de esta manera, es una optimización que casi esperarías, utilizando un patrón de búsqueda bastante específico y afortunado con esta entrada. Excepto cuando se toma en comparación con otros motores, que claramente no hacen este tipo de análisis.

Con /s*/n este no es el caso. Una vez que se encuentra el /n y el carácter anterior no es un espacio, la búsqueda no ha fallado ya que /s* no permite nada (cero caracteres). Tampoco hay subcadenas de longitud fija, y está en el juego de retroceso.

No estoy seguro de los aspectos internos del motor de expresión regular, pero parece que no reconoce que /s+ es de alguna manera igual a /s/s* , ya que en el segundo coincide con un espacio, y luego intenta para que coincida con un número cada vez mayor de espacios, mientras que en el primero, inmediatamente concluye que no hay coincidencia.

La salida usando use re qw( Debug ); muestra claramente esto, usando una cadena mucho más corta:

test_re.pl

#!/usr/bin/env perl use re qw(debug); $x=(" " x 10) . "_/n"; print ''-''x50 . "/n"; $x =~ //s+/n/; print ''-''x50 . "/n"; $x =~ //s/s*/n/; print ''-''x50 . "/n";

Salida

Compiling REx "/s+/n" Final program: 1: PLUS (3) 2: SPACE (0) 3: EXACT </n> (5) 5: END (0) floating "%n" at 1..2147483647 (checking floating) stclass SPACE plus minlen 2 Compiling REx "/s/s*/n" Final program: 1: SPACE (2) 2: STAR (4) 3: SPACE (0) 4: EXACT </n> (6) 6: END (0) floating "%n" at 1..2147483647 (checking floating) stclass SPACE minlen 2 -------------------------------------------------- Guessing start of match in sv for REx "/s+/n" against " _%n" Found floating substr "%n" at offset 11... start_shift: 1 check_at: 11 s: 0 endpos: 11 Does not contradict STCLASS... Guessed: match at offset 0 Matching REx "/s+/n" against " _%n" Matching stclass SPACE against " _" (11 bytes) 0 <> < > | 1:PLUS(3) SPACE can match 10 times out of 2147483647... failed... Contradicts stclass... [regexec_flags] Match failed -------------------------------------------------- Guessing start of match in sv for REx "/s/s*/n" against " _%n" Found floating substr "%n" at offset 11... start_shift: 1 check_at: 11 s: 0 endpos: 11 Does not contradict STCLASS... Guessed: match at offset 0 Matching REx "/s/s*/n" against " _%n" Matching stclass SPACE against " _" (11 bytes) 0 <> < > | 1:SPACE(2) 1 < > < _> | 2:STAR(4) SPACE can match 9 times out of 2147483647... failed... 1 < > < _> | 1:SPACE(2) 2 < > < _> | 2:STAR(4) SPACE can match 8 times out of 2147483647... failed... 2 < > < _> | 1:SPACE(2) 3 < > < _%n> | 2:STAR(4) SPACE can match 7 times out of 2147483647... failed... 3 < > < _%n> | 1:SPACE(2) 4 < > < _%n> | 2:STAR(4) SPACE can match 6 times out of 2147483647... failed... 4 < > < _%n> | 1:SPACE(2) 5 < > < _%n> | 2:STAR(4) SPACE can match 5 times out of 2147483647... failed... 5 < > < _%n> | 1:SPACE(2) 6 < > < _%n> | 2:STAR(4) SPACE can match 4 times out of 2147483647... failed... 6 < > < _%n> | 1:SPACE(2) 7 < > < _%n> | 2:STAR(4) SPACE can match 3 times out of 2147483647... failed... 7 < > < _%n> | 1:SPACE(2) 8 < > < _%n> | 2:STAR(4) SPACE can match 2 times out of 2147483647... failed... 8 < > < _%n> | 1:SPACE(2) 9 < > < _%n> | 2:STAR(4) SPACE can match 1 times out of 2147483647... failed... 9 < > < _%n> | 1:SPACE(2) 10 < > <_%n> | 2:STAR(4) SPACE can match 0 times out of 2147483647... failed... Contradicts stclass... [regexec_flags] Match failed -------------------------------------------------- Freeing REx: "/s+/n" Freeing REx: "/s/s*/n"

Primero, incluso si la expresión regular resultante no mantendrá el mismo significado, reduzcamos las expresiones regulares a /s*0 y /s+0 y usemos (" " x 4) . "_0" (" " x 4) . "_0" como entrada. Para los escépticos, puede ver here que el retraso todavía está presente.

Ahora consideremos el siguiente código:

$x = (" " x 4) . "_ 0"; $x =~ //s*0/; # The slow line $x =~ //s+0/; # The fast line

Excavando un poco con use re debugcolor; obtenemos el siguiente resultado:

Guessing start of match in sv for REx "/s*0" against " _0" Found floating substr "0" at offset 5... start_shift: 0 check_at: 5 s: 0 endpos: 6 checked_upto: 0 Does not contradict STCLASS... Guessed: match at offset 0 Matching REx "/s*0" against " _0" Matching stclass ANYOF_SYNTHETIC[/x09-/x0d 0/x85/xa0][{unicode_all}] against " _0" (6 bytes) 0 < _0>| 1:STAR(3) POSIXD[/s] can match 4 times out of 2147483647... failed... 1 < _0>| 1:STAR(3) POSIXD[/s] can match 3 times out of 2147483647... failed... 2 < _0>| 1:STAR(3) POSIXD[/s] can match 2 times out of 2147483647... failed... 3 < _0>| 1:STAR(3) POSIXD[/s] can match 1 times out of 2147483647... failed... 5 < _0>| 1:STAR(3) POSIXD[/s] can match 0 times out of 2147483647... 5 < _0>| 3: EXACT <0>(5) 6 < _0>| 5: END(0) Match successful! ----------------------- Guessing start of match in sv for REx "/s+0" against " _0" Found floating substr "0" at offset 5... start_shift: 1 check_at: 5 s: 0 endpos: 5 checked_upto: 0 Does not contradict STCLASS... Guessed: match at offset 0 Matching REx "/s+0" against " _0" Matching stclass POSIXD[/s] against " _" (5 bytes) 0 < _0>| 1:PLUS(3) POSIXD[/s] can match 4 times out of 2147483647... failed... Contradicts stclass... [regexec_flags] Match failed

Perl parece estar optimizado para el fracaso . Primero buscará cadenas constantes (que solo consumen O (N)). Aquí buscará 0 : Found floating substr "0" at offset 5...

Luego comenzará con la parte variable de la expresión regular, respectivamente /s* y /s+ , contra toda la cadena mínima para verificar:

Matching REx "/s*0" against " _0" Matching stclass ANYOF_SYNTHETIC[/x09-/x0d 0/x85/xa0][{unicode_all}] against " _0" (6 bytes) Matching REx "/s+0" against " _0" Matching stclass POSIXD[/s] against " _" (5 bytes) # Only 5 bytes because there should be at least 1 "/s" char

Después de eso, buscará la primera posición que cumpla con el requisito de stclass , aquí en la posición 0.

  • /s*0 :
    • comienza en 0, encuentra 4 espacios y luego falla;
    • comienza en 1, encuentra 3 espacios y luego falla;
    • comienza en 2, encuentra 2 espacios y luego falla;
    • comienza en 3, encuentra 1 espacios y luego falla;
    • comienza en 4, encuentra 0 espacios y luego no falla ;
    • Encuentra un 0 exacto
  • /s+0 :
    • comienza en 0, encuentra 4 espacios y luego falla. Como el número mínimo de espacios no coincide, la expresión regular falla instantáneamente.

Si quiere divertirse con la optimización de expresiones regulares de Perl, puede considerar las siguientes expresiones regulares / */n y / * /n . A primera vista, se ven iguales, tienen el mismo significado ... Pero si se ejecuta contra (" " x 40000) . "_/n" (" " x 40000) . "_/n" el primero verificará todas las posibilidades mientras que el segundo buscará " /n" y fallará inmediatamente.

En un motor regex no optimizado, ambos regex pueden causar un retroceso catastrófico, ya que necesitan volver a intentar el patrón a medida que avanza. Sin embargo, en el ejemplo anterior, el segundo no falla con Perl porque se ha optimizado para find floating substr "0%n"

Puedes ver otro ejemplo en el blog de Jeff Atwood .

Tenga en cuenta también que el problema no se trata de /s consideración de /s sino de cualquier patrón en el que se use xx* lugar de x+

Con un ejemplo tan breve, el comportamiento es "encontrable", pero si comienza a jugar con patrones complicados, no es fácil detectarlo, por ejemplo: el programa de bloqueo de expresión regular (100% de uso de CPU)