Présentation des performances des expressions régulières en Java

1. Vue d'ensemble

Dans ce tutoriel rapide, nous montrerons comment fonctionne le moteur de correspondance de modèles. Nous présenterons également différentes manières d'optimiser les expressions régulières en Java.

Pour une introduction à l'utilisation des expressions régulières , veuillez consulter cet article ici.

2. Le moteur de correspondance de motifs

Le package java.util.regex utilise un type de moteur de mise en correspondance de modèles appelé automate fini non déterministe (NFA). Cela est considéré comme non déterministe car tout en essayant de faire correspondre une expression régulière sur une chaîne donnée, chaque caractère de l'entrée peut être vérifié plusieurs fois par rapport à différentes parties de l'expression régulière.

En arrière-plan, le moteur mentionné ci-dessus utilise le retour en arrière . Cet algorithme général essaie d'épuiser toutes les possibilités jusqu'à ce qu'il déclare l'échec. Prenons l'exemple suivant pour mieux comprendre le NFA :

"tra(vel|ce|de)m"

Avec la chaîne d' entrée « travel », le moteur cherchera d'abord « tra » et le trouvera immédiatement.

Après cela, il essaiera de faire correspondre « vel » à partir du quatrième caractère. Cela correspondra, donc il ira de l'avant et essaiera de faire correspondre « m ».

Cela ne correspondra pas, et pour cette raison, il retournera au quatrième caractère et recherchera « ce ». Encore une fois, cela ne correspondra pas, donc il retournera à la quatrième position et essaiera avec « de ». Cette chaîne ne correspondra pas non plus, et elle retournera donc au deuxième caractère de la chaîne d'entrée et essaiera de rechercher un autre « tra ».

Avec le dernier échec, l'algorithme renverra un échec.

Avec le dernier exemple simple, le moteur a dû revenir plusieurs fois en arrière tout en essayant de faire correspondre la chaîne d' entrée à l'expression régulière. Pour cette raison, il est important de minimiser la quantité de retour en arrière qu'il effectue.

3. Moyens d'optimiser les expressions régulières

3.1. Évitez la recompilation

Les expressions régulières en Java sont compilées dans une structure de données interne. Cette compilation est le processus qui prend du temps.

Chaque fois que nous invoquons la méthode String.matches (String regex) , l'expression régulière spécifiée est recompilée:

if (input.matches(regexPattern)) { // do something }

Comme nous pouvons le voir, chaque fois que la condition est évaluée, l'expression regex est compilée.

Pour optimiser, il est possible de compiler d'abord le motif, puis de créer un Matcher pour trouver les coïncidences dans la valeur:

Pattern pattern = Pattern.compile(regexPattern); for(String value : values) { Matcher matcher = pattern.matcher(value); if (matcher.matches()) { // do something } }

Une alternative à l'optimisation ci-dessus consiste à utiliser la même instance de Matcher avec sa méthode reset () :

Pattern pattern = Pattern.compile(regexPattern); Matcher matcher = pattern.matcher(""); for(String value : values) { matcher.reset(value); if (matcher.matches()) { // do something } }

Étant donné que Matcher n'est pas thread-safe, nous devons être prudents avec l'utilisation de cette variante. Cela pourrait être probablement dangereux dans les scénarios multi-threads.

Pour résumer, dans chaque situation où nous sommes sûrs qu'il n'y a qu'un seul utilisateur du Matcher à tout moment, il est possible de le réutiliser avec réinitialisation . Pour le reste, il suffit de réutiliser le précompilé.

3.2. Travailler avec l'alternance

Comme nous venons de le vérifier dans la dernière section, l'utilisation inadéquate des alternances pourrait nuire aux performances. Il est important de placer les options qui sont plus susceptibles de se produire à l'avant afin qu'elles puissent être associées plus rapidement.

En outre, nous devons extraire des modèles communs entre eux. Ce n'est pas la même chose de mettre:

(travel | trade | trace)

Que:

tra(vel | de | ce)

Ce dernier est plus rapide car le NFA essaiera de faire correspondre « tra » et n'essaiera aucune des alternatives s'il ne le trouve pas.

3.3. Capture de groupes

Chaque fois que nous capturons des groupes, nous encourons une petite pénalité.

Si nous n'avons pas besoin de capturer le texte à l'intérieur d'un groupe, nous devrions envisager l'utilisation de groupes sans capture. Au lieu d'utiliser « (M) », veuillez utiliser « (?: M) ».

4. Conclusion

Dans cet article rapide, nous avons brièvement revisité le fonctionnement de NFA . Nous avons ensuite exploré comment optimiser les performances de nos expressions régulières en pré-compilant nos modèles et en réutilisant un Matcher .

Enfin, nous avons souligné quelques considérations à garder à l'esprit lorsque nous travaillons avec des alternances et des groupes.

Comme d'habitude, le code source complet peut être trouvé sur GitHub.