Participer au site avec un Tip
Rechercher
 
Bug Suggérer des Améliorations / Corrections
Share Partager sur Facebook Partager sur Twitter
Links Notre chaîne YouTube Notre discord

Améliorations / Corrections

Vous avez des améliorations (ou des corrections) à proposer pour ce document : je vous remerçie par avance de m'en faire part, cela m'aide à améliorer le site.

Emplacement :

Description des améliorations :

Compilation d'expressions régulières

Nos premières expressions régulières Substitutions via des expressions régulières



Accès rapide :
La vidéo
Pourquoi compiler nos expressions régulières ?
Vérifions l'optimisation
Travaux pratiques

La vidéo

Mal utilisées, les expressions régulières peuvent consommer beaucoup de temps CPU. Il est nécessaire de les compiler (produire la machine à états associée) une fois pour toute plutôt que de le refaire à chaque "matches". C'est ce que cette vidéo vous montre, mesures de performances à l'appui.


Compilation d'expressions régulières

Pourquoi compiler nos expressions régulières ?

Comme nous avons commencé à le voir dans le chapitre précédent, une expression régulière peut être assez complexe. Pour rappels, voici une expression régulière permettant de valider une adresse IPv4 (par ex, 192.168.10.1) : nous en conviendrons tous, elle n'est pas triviale. 

^(([0-9]|[0-9]{2}|[0-1][0-9]{2}|2[0-4][0-9]|25[0-5])\.){3}([0-9]|[0-9]{2}|[0-1][0-9]{2}|2[0-4][0-9]|25[0-5])$
Exemple d'une expression régulière permettant de valider une adresse IPv4

Pour valider si une chaîne quelconque correspond à une expression régulière, une étape intermédiaire est nécessaire. L'expression régulière doit être transformée en une machine à nombre fini d'états (finite state machine, en anglais). Une machine à nombre fini d'états, souvent abrégée en machine à états, permet l'évaluation d'un système en le faisant progressivement passer d'un état à un autre en fonction des transitions rencontrées. L'évaluation de la machine à état s'arrête quand le système atteint un état final (pouvant être associé à un cas de succès ou un cas d'échec). Dans le cas d'une expression régulière, les transitions correspondent aux caractères rencontrés dans la chaîne de caractères à évaluer.

L'utilisation d'une machine à nombre fini d'états, pour l'évaluation de vos expressions régulières, garantie des temps d'exécution optimums. Il faut comprendre que la production de la machine à état n'est liée qu'à l'expression régulière à vérifier et pas aux chaînes de caractères à tester. Cela sous-entend que vous évaluer plusieurs chaînes de caractères correspondant à une adresse IP, vous n'avez besoin de transformer l'expression régulière en une machine à états qu'une seule et unique fois. Si vous le refaites systématiquement à chaque vérification d'adresse, alors vous perdez du temps pour rien. Et gardez en mémoire que cette production de machine à état coûte du temps.

Le problème, c'est que si vous exécutez le programme suivant, alors vous reproduisez une nouvelle machine à état à chaque appel à la méthode isValidAddress 

 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 

public class RegExpMatching {
        
    public static boolean isValidAddress( String address ) {
        String octet = "[0-9]|[0-9]{2}|[0-1][0-9]{2}|2[0-4][0-9]|25[0-5]";
        String regExp = "^((" + octet + ")\\.){3}(" + octet + ")$";
        return address.matches( regExp );
    }
    
    
    public static void main(String[] args) {
        
        // --- Good IPv4 addresses ---
        System.out.println( isValidAddress( "127.0.0.1" ) );
        System.out.println( isValidAddress( "192.168.1.100" ) );
        System.out.println( isValidAddress( "75.78.10.3" ) );
        
        System.out.println( "-----------------------------" );
        
        // --- Bad IPv4 addresses ---
        System.out.println( isValidAddress( "256.1.2.3" ) );
        System.out.println( isValidAddress( "0.256.2.3" ) );
        System.out.println( isValidAddress( "0.1.256.3" ) );
        System.out.println( isValidAddress( "0.1.2.256" ) );
        System.out.println( isValidAddress( "0,1,2,3" ) );
        
    }
    
}
Exemple d'un code Java non optimal en termes d'évaluations multiples d'une expression régulière

L'étape correspondante à la production de la machine à états est appelée « compilation de votre expression régulière ». Il est donc important de sortir la partie de code équivalente à la compilation de l'expression régulière, en dehors de la fonction de vérification. Voici comment réaliser cette optimisation. 

 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 

import java.util.regex.Pattern;

public class RegExpMatching {
        
    private static final String OCTET = "[0-9]|[0-9]{2}|[0-1][0-9]{2}|2[0-4][0-9]|25[0-5]";
    private static final String REG_EXP = "^((" + OCTET + ")\\.){3}(" + OCTET + ")$";
    
    private static final Pattern IP_CHECKER_STATE_MACHINE = Pattern.compile( REG_EXP ); 
    
    
    
    public static boolean isValidAddress( String address ) {              // jj/mm/aaaa    jj/mm/aa
        return IP_CHECKER_STATE_MACHINE.matcher( address ).matches();
    }
    
    
    public static void main(String[] args) {
        
        // --- Good IPv4 addresses ---
        System.out.println( isValidAddress( "127.0.0.1" ) );
        System.out.println( isValidAddress( "192.168.1.100" ) );
        System.out.println( isValidAddress( "75.78.10.3" ) );
        
        System.out.println( "-----------------------------" );
        
        // --- Bad IPv4 addresses ---
        System.out.println( isValidAddress( "256.1.2.3" ) );
        System.out.println( isValidAddress( "0.256.2.3" ) );
        System.out.println( isValidAddress( "0.1.256.3" ) );
        System.out.println( isValidAddress( "0.1.2.256" ) );
        System.out.println( isValidAddress( "0,1,2,3" ) );
        
    }
    
}
Exemple d'une compilation de votre expression régulière
la notion de machine à nombre finis états est implémentée en Java au travers de la classe java.util.regex.Pattern. Pour produire une instance de cette classe, il vous faut invoquer la méthode statique Pattern.compile( String regExp ), comme présenté en ligne 8 de ce programme.

Vérifions l'optimisation

Voici un petit exemple de code mixant les deux approches. Dans les deux cas, nous allons mesurer le temps pour faire un million de vérifications. Il ne restera plus qu'à comparer les deux temps obtenus pour voir quelle est l'approche la plus efficace. 

 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 

import java.util.regex.Pattern;

public class RegExpPerf {
        
    private static final String OCTET = "[0-9]|[0-9]{2}|[0-1][0-9]{2}|2[0-4][0-9]|25[0-5]";
    private static final String REG_EXP = "^((" + OCTET + ")\\.){3}(" + OCTET + ")$";
    
    private static final Pattern IP_CHECKER_STATE_MACHINE = Pattern.compile( REG_EXP ); 
    
    
    public static boolean isValidAddress( String address ) {              // jj/mm/aaaa    jj/mm/aa
        return IP_CHECKER_STATE_MACHINE.matcher( address ).matches();
    }

    public static boolean isValidAddressOld( String address ) {           // jj/mm/aaaa    jj/mm/aa
        return address.matches( REG_EXP );
    }

    
    public static void main(String[] args) {

        long begin = System.currentTimeMillis();
        
        for( int i=0; i<1_000_000; i++ ) {
            isValidAddressOld( "192.168.1.100" );
        }
        
        long end = System.currentTimeMillis();
        System.out.println( "Duration Before Optims: " + (end-begin) + "ms" );

        
        
        begin = System.currentTimeMillis();
        
        for( int i=0; i<1_000_000; i++ ) {
            isValidAddress( "192.168.1.100" );
        }
        
        end = System.currentTimeMillis();
        System.out.println( "Duration After Optims: " + (end-begin) + "ms" );
        
    }
    
}
Comparons avec et sans compilation de l'expression régulière

Et voici maintenant les temps de réponses obtenus. Je pense que les résultats sont sans appels. 

$> java RegExpPerf
Duration Before Optims: 2157ms
Duration After Optims: 342ms
$>

Travaux pratiques

En guise de travaux pratiques, vous pouvez reprendre les exemples proposés dans le chapitre précédent et les optimiser en y compilant préalablement les expressions régulières présentes.



Nos premières expressions régulières Substitutions via des expressions régulières