¿La expresión regular de Java ofrece algún beneficio de rendimiento?

Question

En Java, cuando tratamos de hacer la coincidencia de patrones utilizando una expresión regular. p.ej. tomar una cadena de entrada y usar expresión regular para averiguar si es numérica. Si no, lanza una excepción. En este caso, entiendo, usar regex hace que el código sea menos detallado que si tomáramos cada carácter de la cadena, verificamos si es un número y si no lanzamos una excepción.

Pero yo estaba bajo la suposición de que la expresión regular también hace que el proceso sea más eficiente. ¿Es esto cierto? No puedo encontrar ninguna evidencia sobre este punto. ¿Cómo está Regex haciendo el partido detrás de escena? ¿No está iterando sobre la cadena y revisando cada carácter uno por uno?

Answer 1

Solo por diversión, he ejecutado este micro benchmark. Los resultados de la última ejecución (es decirJVM después de calentamiento/JIT) están por debajo (los resultados son bastante consistentes de una carrera a otra de todos modos):

regex with numbers 123 
chars with numbers 33 
parseInt with numbers 33 
regex with words 123 
chars with words 34 
parseInt with words 733 

En otras palabras, caracteres es muy eficiente, Integer.parseInt es tan eficiente como char si la cadena es un número, pero muy lento si la cadena no es un número. Regex está en el medio.

Conclusión

Si analizar una cadena en un número y se espera que la cadena a ser un número en general, utilizando Integer.parseInt es la mejor solución (eficiente y legible). La penalización que recibe cuando la cuerda no es un número debe ser baja si no es demasiado frecuente.

ps: mi expresión regular quizás no sea óptima, no dude en comentar.

public class TestNumber { 

    private final static List<String> numbers = new ArrayList<>(); 
    private final static List<String> words = new ArrayList<>(); 

    public static void main(String args[]) { 
     long start, end; 
     Random random = new Random(); 

     for (int i = 0; i < 1000000; i++) { 
      numbers.add(String.valueOf(i)); 
      words.add(String.valueOf(i) + "x"); 
     } 

     for (int i = 0; i < 5; i++) { 
      start = System.nanoTime(); 
      regex(numbers); 
      System.out.println("regex with numbers " + (System.nanoTime() - start)/1000000); 
      start = System.nanoTime(); 
      chars(numbers); 
      System.out.println("chars with numbers " + (System.nanoTime() - start)/1000000); 
      start = System.nanoTime(); 
      exception(numbers); 
      System.out.println("exceptions with numbers " + (System.nanoTime() - start)/1000000); 

      start = System.nanoTime(); 
      regex(words); 
      System.out.println("regex with words " + (System.nanoTime() - start)/1000000); 
      start = System.nanoTime(); 
      chars(words); 
      System.out.println("chars with words " + (System.nanoTime() - start)/1000000); 
      start = System.nanoTime(); 
      exception(words); 
      System.out.println("exceptions with words " + (System.nanoTime() - start)/1000000); 
     } 
    } 

    private static int regex(List<String> list) { 
     int sum = 0; 
     Pattern p = Pattern.compile("[0-9]+"); 
     for (String s : list) { 
      sum += (p.matcher(s).matches() ? 1 : 0); 
     } 
     return sum; 
    } 

    private static int chars(List<String> list) { 
     int sum = 0; 

     for (String s : list) { 
      boolean isNumber = true; 
      for (char c : s.toCharArray()) { 
       if (c < '0' || c > '9') { 
        isNumber = false; 
        break; 
       } 
      } 
      if (isNumber) { 
       sum++; 
      } 
     } 
     return sum; 
    } 

    private static int exception(List<String> list) { 
     int sum = 0; 

     for (String s : list) { 
      try { 
       Integer.parseInt(s); 
       sum++; 
      } catch (NumberFormatException e) { 
      } 
     } 
     return sum; 
    } 
} 

Answer 2

Todavía no tengo una respuesta técnica, pero podría escribir un código y ver. No creo que las expresiones regulares sean el camino a seguir para convertir una cadena en un número. En muchos casos, pueden ser más eficientes, pero si se escribe mal, será lento.

Puedo preguntar sin embargo, ¿por qué no estás usando: Integer.parseInt("124")? Eso arrojará una NumberFormatException. Debería poder manejarlo, y deja la detección de un número hasta el núcleo de Java.

Answer 3

Bueno, es difícil decirlo con certeza, pero en general las expresiones regulares tienen menos probabilidades de ser más eficientes en comparación con la comprobación explícita de caracteres. RE es un autómata de estado final, por lo que hay cierta sobrecarga en la construcción y mantenimiento de autómatas. En mi práctica, el código explícito es siempre más rápido (y por lo tanto más eficiente) que las expresiones regulares.

Pero aquí está el dilema. Las expresiones regulares son casi siempre más eficientes desde el punto de vista del tiempo de entrega y más legibles si se usan correctamente. Y aquí hay otro dilema. Yo por lo que rara vez se ve el uso correcto de las expresiones regulares ...

En su escenario Es mejor utilizar la biblioteca de guayaba:

boolean isValid = DIGIT.matchesAllOf("1234"); 

Answer 4

Al final, es, en efecto interactuando sobre la cuerda y la comprobación de cada personaje tratando para encontrar coincidencias para el patrón proporcionado. Además, utiliza el rastreo (si hay muchas maneras en que podría coincidir, el motor las probará todas), lo que podría dar como resultado un rendimiento muy bajo en algunos casos inusuales (no es probable que te encuentres con esto, pero teóricamente es posible). En el peor de los casos, el rendimiento del motor de expresiones regulares de Java es O (2 ^N), donde N es la longitud de la cadena de entrada.

Existen algoritmos para una coincidencia de patrones mucho más rápida que ofrece un rendimiento de O (N) pero con menos características en comparación con las expresiones regulares de Java.

Here es un artículo sobre esta cuestión en detalle.

Pero en la mayoría de los casos, el motor de expresión regular no será el cuello de botella de rendimiento en su aplicación. Es lo suficientemente rápido, por lo que, en general, no te preocupes a menos que tu generador de perfiles lo señale. Y proporciona una descripción declarativa del algoritmo que es muy útil porque casi siempre la implementación de algoritmos iterativos será mucho más prolija y mucho menos legible.

Answer 5

Para responder a su pregunta en concreto:

¿Por qué no se aplica un ajuste de patrones de expresiones regulares sobre un texto complejo, y luego tratar de escribir el mismo código coincidente mismo.

Vea cuál es más rápido.

Respuesta: The regex.

Answer 6

Acerca de expresiones regulares detrás de las escenas ...

Un máquina de estados finitos (FSM) es equivalente a una expresión regular. FSM es una máquina que puede reconocer un idioma (en su número de caso). FSM tiene un alfabeto, estados, un estado inicial, estados N-finales y funciones de transición de un estado a otro. La cadena debe contenerse en el alfabeto (ASCII, por ejemplo). El FSM comienza en el estado inicial. Cuando ingresa una cadena, procesa char por char moviéndose de un estado a otro dependiendo de una función (estado, char) => estado. Cuando alcanza un estado final, usted sabe si su cadena es numérica o no.

Para más información, véase el FSM y ver Automata-based_programming

Answer 7

no veo cómo podría ser más simple o más fácil de leer que:

Integer.parseInt()

o

Double.parseDouble()

Ellos hacen exactamente lo que describes, incluyendo lanzar una excepción para i entrada nvalid.

En cuanto a rendimiento: esperaría que una expresión regular fuera menos eficiente que la anterior.

Answer 8

Just my 5 centavos :) En general, el lenguaje de expresiones regulares no está destinado a analizar únicamente enteros o cadenas, es una herramienta bastante poderosa que permite reconocer cualquier 'expresión regular'. Me recuerda mi tiempo en la universidad (¿Recuerdas el curso de Teoría de Automatas?:), pero aquí es la link que describe lo que el lenguaje regular es realmente

Ahora ya que se basa FSM crea algo de sobrecarga, por lo que tal vez por Integer.parseInt motor de expresiones regulares no es una buena sustitución, además de Java introdujo la API más específica . Sin embargo, las expresiones regulares tienen un beneficio cuando se trabaja con expresiones más complejas y cuando tenemos muchas de ellas.

La expresión regular debe utilizarse con prudencia. El patrón debe compilarse siempre (de lo contrario, no se puede reutilizar de manera eficiente, ya que compilar el patrón cada vez se agotará el rendimiento)

Yo sugeriría ejecutar la prueba en una entrada más compleja y ver qué pasa.