L'espressione regolare Java offre vantaggi in termini di prestazioni?

Question

In Java, quando si tenta di eseguire la corrispondenza del modello utilizzando un'espressione regolare. per esempio. prendi una stringa di input e usa espressioni regolari per scoprire se è numerica. In caso contrario, lanciare un'eccezione. In questo caso, capisco, l'uso della regex rende il codice meno dettagliato di se dovessimo prendere ogni carattere della stringa, controllare se è un numero e se non lanciare un'eccezione.

Ma ero sotto il presupposto che regex rende anche il processo più efficiente. È vero? Non riesco a trovare alcuna prova su questo punto. In che modo regex fa la partita dietro le quinte? Non sta forse iterando oltre la stringa e controllando ogni personaggio uno per uno?

Answer 1

Solo per divertimento, ho eseguito questo micro punto di riferimento. I risultati dell'ultima analisi (es.alberino JVM riscaldare/JIT) sono inferiori (risultati sono abbastanza consistente da una corsa all'altra comunque):

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

In altre parole, caratteri è molto efficiente, Integer.parseInt è efficiente come char se la stringa è un numero, ma terribilmente lento se la stringa non è un numero. Regex è nel mezzo.

Conclusione

Se si analizza una stringa in un numero e ci si aspetta la stringa da un numero, in generale, utilizzando Integer.parseInt è la soluzione migliore (efficiente e leggibile). La penalità che si ottiene quando la stringa non è un numero dovrebbe essere bassa se non è troppo frequente.

ps: la mia espressione regolare forse non è ottimale, non esitate a commentare.

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

Non ho ancora una risposta tecnica, ma potrei scrivere del codice e vedere. Non penso che le espressioni regolari siano la strada da percorrere per convertire una stringa in un numero. In molti casi possono essere più efficienti, ma se scritti male, saranno lenti.

Posso chiedere tuttavia, perché non stai usando solo: Integer.parseInt("124")? Ciò genererà una NumberFormatException. Dovrebbe essere in grado di gestirlo e lascia il rilevamento di un numero fino a core Java.

Answer 3

Beh, è ​​difficile dirlo con certezza, ma in generale le espressioni regolari hanno meno probabilità di essere più efficienti rispetto al controllo esplicito dei caratteri. RE è un automa di stato finale, quindi c'è un sovraccarico sulla creazione e sul mantenimento degli automi. Nella mia pratica il codice esplicito è sempre più veloce (e quindi più efficiente) rispetto alle espressioni regolari.

Ma ecco il dilemma. Le espressioni regolari sono quasi sempre più efficienti dal punto di vista del time-to-deliver e più leggibili se usate correttamente. E qui c'è un altro dilemma. Ho così raramente vedo corretta utilizzo delle espressioni regolari ...

Nel tuo scenario Suggerisco di usare libreria di guava:

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

Answer 4

Alla fine si è infatti scorrere il corda e controllando ogni carattere cercando per trovare la corrispondenza per il modello fornito. Inoltre utilizza il backtracking (se ci sono molti modi che potrebbero corrispondere, il motore li proverà tutti), il che potrebbe comportare prestazioni molto scarse per alcuni casi insoliti (non è probabile che lo si incontrerà, ma teoricamente possibile). Nel peggiore dei casi le prestazioni del motore di espressioni regolari java sono O (2 ^N), dove N è la lunghezza della stringa di input.

Esistono algoritmi per la corrispondenza di modelli molto più rapida che offrono prestazioni O (N) ma con meno funzioni rispetto alle espressioni regolari Java.

Here è un articolo che tratta questa domanda in dettaglio.

Ma nella maggior parte dei casi il motore di espressioni regolari non sarà il collo di bottiglia delle prestazioni nell'applicazione. È abbastanza veloce, quindi generalmente non ti preoccupare a meno che il tuo profiler non punti ad esso. E fornisce una descrizione dichiarativa dell'algoritmo che è molto utile perché l'implementazione quasi sempre iterativa dell'algoritmo sarà molto più prolissa e molto meno leggibile.

Answer 5

Per rispondere alla tua domanda in particolare:

Perché non si applica un pattern match regex su qualche testo complesso, e quindi tentare di scrivere lo stesso codice corrispondente da soli.

Vedere quale è più veloce.

Risposta: Il regex.

Answer 6

Chi regex dietro le quinte ...

Un macchina a stati finiti (FSM) è equivalente a un'espressione regolare. FSM è una macchina in grado di riconoscere una lingua (nel tuo caso numeri). L'FSM ha un alfabeto, stati, uno stato iniziale, stati N-finali e funzioni di transizione da uno stato all'altro. La stringa deve essere contenuta nell'alfabeto (ASCII ad esempio). L'FSM inizia allo stato iniziale. Quando inserisci una stringa, elabora char per char spostandosi da stato a stato a seconda di una funzione (stato, char) => stato. Quando raggiunge uno stato finale, sai se la stringa è numerica o meno.

Per ulteriori informazioni, consultare FSM e vedere Automata-based_programming

Answer 7

non vedo come potrebbe essere più semplice o più facile da leggere rispetto:

Integer.parseInt()

o

Double.parseDouble()

Fanno esattamente ciò che descrivono, tra cui un'eccezione per i input non valido.

Per quanto riguarda le prestazioni: mi aspetto che una regex sia meno efficiente di quanto sopra.

Answer 8

Solo i miei 5 centesimi :) In generale, il linguaggio delle espressioni non è inteso solo per analizzare gli interi o le stringhe, è uno strumento piuttosto potente che consente di riconoscere qualsiasi 'espressione regolare'. Mi ricorda il mio periodo universitario (ricorda il corso Teoria degli automi?:), ma qui è la link che descrive ciò che il linguaggio regolare è davvero

Ora, dato che produce FSM che introduce un certo overhead, quindi forse per Integer.parseInt normale motore di espressione non è una buona sostituzione, inoltre Java ha introdotto l'API più specifica . Tuttavia le espressioni regolari hanno un vantaggio quando si lavora con espressioni più complesse e quando ne abbiamo molte.

L'espressione regolare deve essere utilizzata con saggezza. Il pattern deve essere sempre compilato (altrimenti non può essere riutilizzato in modo efficiente, poiché la compilazione del pattern ogni volta prosciugherà le prestazioni)

Vorrei suggerire di eseguire il test su input più complessi e vedere cosa succede.