1. Información general
En este tutorial rápido, mostraremos cómo funciona el motor de coincidencia de patrones. También presentaremos diferentes formas de optimizar expresiones regulares en Java.
Para obtener una introducción al uso de expresiones regulares , consulte este artículo aquí.
2. El motor de coincidencia de patrones
El paquete java.util.regex utiliza un tipo de motor de coincidencia de patrones llamado Autómata finito no determinista (NFA). Se considera no determinista porque al intentar hacer coincidir una expresión regular en una cadena determinada, cada carácter de la entrada puede comprobarse varias veces con diferentes partes de la expresión regular.
En segundo plano, el motor mencionado anteriormente utiliza retroceso . Este algoritmo general intenta agotar todas las posibilidades hasta que declara falla. Considere el siguiente ejemplo para comprender mejor la NFA :
"tra(vel|ce|de)m"Con la cadena de entrada " viaje ", el motor primero buscará " tra " y lo encontrará inmediatamente.
Después de eso, intentará hacer coincidir " vel " a partir del cuarto carácter. Esto coincidirá, por lo que avanzará e intentará coincidir con " m ".
Eso no coincidirá, y por esa razón, volverá al cuarto carácter y buscará " ce ". Una vez más, esto no coincidirá, por lo que volverá a la cuarta posición e intentará con " de ". Esa cadena tampoco coincidirá, por lo que volverá al segundo carácter de la cadena de entrada e intentará buscar otra " tra ".
Con la última falla, el algoritmo devolverá la falla.
Con el último ejemplo simple, el motor tuvo que retroceder varias veces al intentar hacer coincidir la cadena de entrada con la expresión regular. Por eso, es importante minimizar la cantidad de retroceso que hace.
3. Formas de optimizar las expresiones regulares
3.1. Evite la recompilación
Las expresiones regulares en Java se compilan en una estructura de datos interna. Esta compilación es un proceso que requiere mucho tiempo.
Cada vez que invocamos el método String.matches (String regex) , se vuelve a compilar la expresión regular especificada:
if (input.matches(regexPattern)) { // do something }Como podemos ver, cada vez que se evalúa la condición, se compila la expresión regex.
Para optimizar, es posible compilar el patrón primero y luego crear un Matcher para encontrar las coincidencias en el valor:
Pattern pattern = Pattern.compile(regexPattern); for(String value : values) { Matcher matcher = pattern.matcher(value); if (matcher.matches()) { // do something } }Una alternativa a la optimización anterior es usar la misma instancia de Matcher con su método reset () :
Pattern pattern = Pattern.compile(regexPattern); Matcher matcher = pattern.matcher(""); for(String value : values) { matcher.reset(value); if (matcher.matches()) { // do something } }Debido al hecho de que Matcher no es seguro para subprocesos, debemos tener cuidado con el uso de esta variación. Probablemente podría ser peligroso en escenarios de subprocesos múltiples.
Para resumir, en cada situación en la que estamos seguros de que solo hay un usuario del Matcher en cualquier momento, está bien reutilizarlo con reinicio . Por lo demás, reutilizar el precompilado es suficiente.
3.2. Trabajar con alternancia
Como acabamos de comprobar en la última sección, el uso inadecuado de alternancias podría ser perjudicial para el rendimiento. Es importante colocar las opciones que tienen más probabilidades de suceder al principio para que se puedan combinar más rápido.
Además, tenemos que extraer patrones comunes entre ellos. No es lo mismo poner:
(travel | trade | trace)Que:
tra(vel | de | ce)Este último es más rápido porque la NFA intentará hacer coincidir " tra " y no probará ninguna de las alternativas si no lo encuentra.
3.3. Capturar grupos
Cada vez que capturamos grupos, incurrimos en una pequeña penalización.
Si no necesitamos capturar el texto dentro de un grupo, deberíamos considerar el uso de grupos que no capturan. En lugar de utilizar " (M) ", utilice " (?: M) ".
4. Conclusión
En este artículo rápido, revisamos brevemente cómo funciona NFA . Luego procedimos a explorar cómo optimizar el rendimiento de nuestras expresiones regulares compilando previamente nuestros patrones y reutilizando un Matcher .
Finalmente, señalamos un par de consideraciones a tener en cuenta mientras trabajamos con alternancias y grupos.
Como de costumbre, el código fuente completo se puede encontrar en GitHub.