Comparando la velocidad de la expresión regular no coincidente

El siguiente código de Python es increíblemente lento:

import re re.match( '([a]+)+c', 'a' * 30 + 'b' ) 

y empeora si reemplazas 30 con una constante más grande.

Sospecho que la ambigüedad del análisis debido al + consecutivo es el culpable, pero no soy muy experto en el análisis y la comparación de expresiones regulares. ¿Es esto un error del motor de expresión regular de Python, o cualquier implementación razonable hará lo mismo?

No soy un experto en Perl, pero lo siguiente vuelve bastante rápido

 perl -e '$s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"; print "ok\n" if $s =~ m/([a]+)+c/;' 

y boost el número de ‘a’ no altera sustancialmente la velocidad de ejecución.

Supongo que Perl es lo suficientemente inteligente como para colapsar los dos + s en uno, mientras que Python no lo es. Ahora imaginemos lo que hace el motor, si esto no se optimiza. Y recuerda que la captura es generalmente costosa. Tenga en cuenta también que ambos + s son codiciosos, por lo que el motor intentará usar tantas repeticiones como sea posible en un paso de retroceso. Cada punto de viñeta representa un paso de retroceso:

  • El motor usa tantos [a] como sea posible, y consume todos los treinta a s. Entonces no puede ir más lejos, por lo que deja la primera repetición y captura 30 a s. Ahora la siguiente repetición está activada y trata de consumir más con otra ([a]+) pero eso no funciona, por supuesto. Y luego la c no coincide con b .
  • ¡Volver hacia atrás! Deseche el último a consumido por la repetición interior. Después de esto volvemos a dejar la repetición interior, para que el motor capture 29 a s. Luego, el otro + entra en acción, se repite la repetición interna (consumiendo la 30a a ). Luego dejamos la repetición interna una vez más, lo que también deja al grupo de captura, por lo que la primera captura se tira y el motor captura la última a . c no puede coincidir b .
  • ¡Volver hacia atrás! Tirar otro a dentro. Capturamos 28 a s. La segunda (repetición externa) del grupo de captura consume los últimos 2 a que se capturan . c no puede coincidir b .
  • ¡Volver hacia atrás! Ahora podemos retroceder en la segunda repetición y tirar la segunda de dos a s. El que queda será capturado . Luego ingresamos al grupo de captura por tercera vez y capturamos la última a . c no puede coincidir b .
  • ¡Volver hacia atrás! Hasta 27 a s en la primera repetición.

Aquí hay una visualización simple. Cada línea representa un paso de retroceso, y cada conjunto de paréntesis muestra un consumo de la repetición interna. Los corchetes representan los que se capturaron recientemente para ese paso de retroceso, mientras que los paréntesis normales no se revisan en este paso de retroceso en particular. Y omito el b / c porque nunca será igualado:

 {aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} {aaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{a} {aaaaaaaaaaaaaaaaaaaaaaaaaaaa}{aa} (aaaaaaaaaaaaaaaaaaaaaaaaaaaa){a}{a} {aaaaaaaaaaaaaaaaaaaaaaaaaaa}{aaa} (aaaaaaaaaaaaaaaaaaaaaaaaaaa){aa}{a} (aaaaaaaaaaaaaaaaaaaaaaaaaaa){a}{aa} (aaaaaaaaaaaaaaaaaaaaaaaaaaa)(a){a}{a} {aaaaaaaaaaaaaaaaaaaaaaaaaa}{aaaa} (aaaaaaaaaaaaaaaaaaaaaaaaaa){aaa}{a} (aaaaaaaaaaaaaaaaaaaaaaaaaa){aa}{aa} (aaaaaaaaaaaaaaaaaaaaaaaaaa)(aa){a}{a} (aaaaaaaaaaaaaaaaaaaaaaaaaa){a}{aaa} (aaaaaaaaaaaaaaaaaaaaaaaaaa)(a){aa}{a} (aaaaaaaaaaaaaaaaaaaaaaaaaa)(a){a}{aa} (aaaaaaaaaaaaaaaaaaaaaaaaaa)(a)(a){a}{a} 

Y. asi que. en.

Tenga en cuenta que, al final, el motor también probará todas las combinaciones para los subconjuntos de (retroceder solo los primeros 29 a s y luego los primeros 28 a s) solo para descubrir que c no coincide con a .

La explicación de los componentes internos del motor de expresiones regulares se basa en la información dispersa alrededor de regular-expressions.info .

Para resolver esto. Simplemente quite uno de los + s. O r'a+c' o si desea capturar la cantidad de a s use r'(a+)s' .

Por último, para responder a su pregunta. No consideraría esto como un error en el motor de expresiones regulares de Python, sino solo (si acaso) una falta en la lógica de optimización. Este problema generalmente no es solucionable, por lo que no es demasiado irrazonable que un motor asum que tiene que hacerse cargo de un retroceso catastrófico usted mismo. Si Perl es lo suficientemente inteligente como para reconocer casos suficientemente simples, tanto mejor.

Reescriba su expresión regular para eliminar el “retroceso catastrófico” , eliminando los cuantificadores nesteds (vea esta pregunta ):

 re.match( '([a]+)+c', 'a' * 30 + 'b' ) # becomes re.match( 'a+c', 'a' * 30 + 'b' )