0
162
Vistas¿Por qué esta expresión regular es tan lenta en Java?
Recientemente tuve una regla de SonarQube ( https://rules.sonarsource.com/java/RSPEC-4784 ) que me llamó la atención sobre algunos problemas de rendimiento que podrían usarse como una denegación de servicio contra una implementación de expresiones regulares de Java.
De hecho, la siguiente prueba de Java muestra cuán lenta puede ser la expresión regular incorrecta:
import org.junit.Test; public class RegexTest { @Test public void fastRegex1() { "aaaaaaaaaaaaaaaaaaaaaaaaaaaabs".matches("(a+)b"); } @Test public void fastRegex2() { "aaaaaaaaaaaaaaaaaaaaaaaaaaaab".matches("(a+)+b"); } @Test public void slowRegex() { "aaaaaaaaaaaaaaaaaaaaaaaaaaaabs".matches("(a+)+b"); } }Como puede ver, las dos primeras pruebas son rápidas, la tercera es increíblemente lenta (en Java 8)
Sin embargo, los mismos datos y expresiones regulares en Perl o Python no son nada lentos, lo que me lleva a preguntarme por qué esta expresión regular es tan lenta de evaluar en Java.
$ time perl -e '"aaaaaaaaaaaaaaaaaaaaaaaaaaaabs" =~ /(a+)+b/ && print "$1\n"' aaaaaaaaaaaaaaaaaaaaaaaaaaaa real 0m0.004s user 0m0.000s sys 0m0.004s $ time python3 -c 'import re; m=re.search("(a+)+b","aaaaaaaaaaaaaaaaaaaaaaaaaaaabs"); print(m.group(0))' aaaaaaaaaaaaaaaaaaaaaaaaaaaab real 0m0.018s user 0m0.015s sys 0m0.004s ¿Qué tiene el modificador de coincidencia adicional + o el carácter final s en los datos que hace que esta expresión regular sea tan lenta y por qué solo es específica de Java?
4 Respuestas
Responde la pregunta0
El + adicional provoca muchos retrocesos (en una implementación ingenua de expresiones regulares) cuando no se puede hacer coincidir la cadena. Si se puede hacer coincidir la cadena, la respuesta se conoce en el primer intento. Esto explica por qué el caso 2 es rápido y solo el caso 3 es lento.
0
Advertencia: Realmente no sé mucho sobre las expresiones internas de expresiones regulares, y esto es realmente una conjetura. Y no puedo responder por qué Java sufre esto, pero no los demás (además, es sustancialmente más rápido que sus 12 segundos en jshell 11 cuando lo ejecuto, por lo que quizás solo afecte a ciertas versiones).
"aaaaaaaaaaaaaaaaaaaaaaaaaaaabs".matches("(a+)+b") Hay muchas maneras a que muchas s podrían coincidir:
(a)(a)(a)(a) (aa)(a)(a) (a)(aa)(a) (aa)(aa) (a)(aaa) etc. Para la cadena de entrada "aaaaaaaaaaaaaaaaaaaaaaaaaaaab" , coincidirá con avidez con todos esos a s en un solo paso, coincidirá con la b , trabajo hecho.
Para "aaaaaaaaaaaaaaaaaaaaaaaaaaaabs" , cuando llega al final y descubre que la cadena no coincide (debido a la s ), no reconoce correctamente que la s significa que nunca puede coincidir. Entonces, habiendo pasado y probablemente emparejado como
(aaaaaaaaaaaaaaaaaaaaaaaaaaaa)bs piensa "Oh, tal vez falló debido a la forma en que agrupé las a s - y regresa e intenta todas las otras combinaciones de las a s.
(aaaaaaaaaaaaaaaaaaaaaaaaaaa)(a)bs // Nope, still no match (aaaaaaaaaaaaaaaaaaaaaaaaaa)(aa)bs // ... (aaaaaaaaaaaaaaaaaaaaaaaaa)(aaa)bs // ... ... (a)(aaaaaaaaaaaaaaaaaaaaaaaaaaa)bs // ... (aaaaaaaaaaaaaaaaaaaaaaaaaa(a)(a)bs // ... (aaaaaaaaaaaaaaaaaaaaaaaaa(aa)(a)bs // ... (aaaaaaaaaaaaaaaaaaaaaaaa(aaa)(a)bs // ... ... Hay muchos de estos (creo que hay algo así como 2 ^ 27, eso es 134,217,728, combinaciones para 28 a s, porque cada a puede ser parte del grupo anterior o comenzar su propio grupo), por lo que toma mucho tiempo .
0
No conozco muy bien Perl, pero la versión de Python no es equivalente a la de Java. Está usando search() pero la versión de Java está usando matches() . El método equivalente en Python sería fullmatch()
Cuando ejecuto sus ejemplos en Python (3.8.2) con search() , obtengo resultados rápidos como usted. Cuando lo ejecuto con fullmatch() obtengo un tiempo de ejecución pobre (de varios segundos). ¿Podría ser que su ejemplo de Perl tampoco esté haciendo una coincidencia completa?
Por cierto: si quieres probar la versión de búsqueda de Java, usarías:
Pattern.compile("(a+)+b").matcher("aaaaaaaaaaaaaaaaaaaaaaaaaaaabs").find();Puede haber alguna ligera diferencia en la semántica, pero debería ser lo suficientemente parecida para este propósito.
0
El sitio https://swtch.com/~rsc/regexp/regexp1.html tiene información detallada sobre las técnicas de implementación de expresiones regulares y la teoría detrás de ellas. Sé que las respuestas de solo enlace son malas, pero vale la pena leer esto, que muestra un ejemplo de expresión regular que se completa en 30 microsegundos con la mejor implementación, y 60 segundos (2 millones de veces más lento) con la forma más conocida y más obvia.
Dice
"Hoy en día, las expresiones regulares también se han convertido en un brillante ejemplo de cómo ignorar una buena teoría conduce a malos programas. Las implementaciones de expresiones regulares utilizadas por las herramientas populares de hoy en día son significativamente más lentas que las utilizadas en muchas de esas herramientas Unix de hace treinta años".
Otras respuestas que dicen que el + adicional causa demasiado retroceso son correctas, pero solo si ignora la buena teoría.