Java Language Piège - Problèmes d’efficacité avec les expressions régulières


Exemple

La correspondance d'expressions régulières est un outil puissant (en Java et dans d'autres contextes), mais elle présente certains inconvénients. Une de ces expressions que les expressions régulières ont tendance à être assez chère.

Les instances Pattern et Matcher doivent être réutilisées

Prenons l'exemple suivant:

/**
 * Test if all strings in a list consist of English letters and numbers.
 * @param strings the list to be checked
 * @return 'true' if an only if all strings satisfy the criteria
 * @throws NullPointerException if 'strings' is 'null' or a 'null' element.
 */
public boolean allAlphanumeric(List<String> strings) {
    for (String s : strings) {
        if (!s.matches("[A-Za-z0-9]*")) {
            return false;
        }  
    }
    return true;
}

Ce code est correct, mais il est inefficace. Le problème réside dans l'appel de matches(...) . Sous le capot, s.matches("[A-Za-z0-9]*") est équivalent à ceci:

Pattern.matches(s, "[A-Za-z0-9]*")

ce qui équivaut à son tour à

Pattern.compile("[A-Za-z0-9]*").matcher(s).matches()

L' Pattern.compile("[A-Za-z0-9]*") analyse l'expression régulière, l'analyse et construit un objet Pattern contenant la structure de données qui sera utilisée par le moteur regex. C'est un calcul non trivial. Ensuite, un objet Matcher est créé pour envelopper l'argument s . Enfin, nous appelons match() pour faire la correspondance de motif réelle.

Le problème est que ce travail est répété pour chaque itération de boucle. La solution consiste à restructurer le code comme suit:

private static Pattern ALPHA_NUMERIC = Pattern.compile("[A-Za-z0-9]*");

public boolean allAlphanumeric(List<String> strings) {
    Matcher matcher = ALPHA_NUMERIC.matcher("");
    for (String s : strings) {
        matcher.reset(s);
        if (!matcher.matches()) {
            return false;
        }  
    }
    return true;
}

Notez que le javadoc pour Pattern indique:

Les instances de cette classe sont immuables et peuvent être utilisées par plusieurs threads simultanés. Les instances de la classe Matcher ne sont pas sûres pour une telle utilisation.

N'utilisez pas match () quand vous devriez utiliser find ()

Supposons que vous voulez tester si une chaîne s contient trois chiffres ou plus dans une rangée. Vous pouvez l'exprimer de différentes manières, notamment:

  if (s.matches(".*[0-9]{3}.*")) {
      System.out.println("matches");
  }

ou

  if (Pattern.compile("[0-9]{3}").matcher(s).find()) {
      System.out.println("matches");
  }

Le premier est plus concis, mais il est également susceptible d'être moins efficace. À première vue, la première version va essayer de faire correspondre la chaîne entière au motif. De plus, puisque ". *" Est un modèle "gourmand", le gestionnaire de motifs est susceptible de faire avancer "avidement" la fin de la chaîne et de revenir en arrière jusqu'à ce qu'il trouve une correspondance.

En revanche, la deuxième version recherchera de gauche à droite et cessera de chercher dès qu'elle trouvera les 3 chiffres à la suite.

Utiliser des alternatives plus efficaces aux expressions régulières

Les expressions régulières sont un outil puissant, mais elles ne doivent pas être votre seul outil. Beaucoup de tâches peuvent être effectuées de manière plus efficace par d'autres moyens. Par exemple:

 Pattern.compile("ABC").matcher(s).find()

fait la même chose que:

 s.contains("ABC")

sauf que ce dernier est beaucoup plus efficace. (Même si vous pouvez amortir le coût de compilation de l'expression régulière)

Souvent, la forme non-regex est plus compliquée. Par exemple, le test effectué par l'appel matches() la méthode allAlplanumeric antérieure peut être réécrit comme allAlplanumeric :

 public boolean matches(String s) {
     for (char c : s) {
         if ((c >= 'A' && c <= 'Z') ||
             (c >= 'a' && c <= 'z') ||
             (c >= '0' && c <= '9')) {
              return false;
         }
     }
     return true;
 }

Maintenant, c'est plus de code que d'utiliser un Matcher , mais cela va être beaucoup plus rapide.

Retournement catastrophique

(Ceci est potentiellement un problème avec toutes les implémentations d'expressions régulières, mais nous allons le mentionner ici car c'est un piège pour l'utilisation de Pattern .)

Considérons cet exemple (artificiel):

Pattern pat = Pattern.compile("(A+)+B");
System.out.println(pat.matcher("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB").matches());
System.out.println(pat.matcher("AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC").matches());

Le premier println appel va rapidement imprimer true . Le second imprimera false . Finalement. En effet, si vous testez le code ci-dessus, vous verrez que chaque fois que vous ajoutez un A avant le C , le temps nécessaire doublera.

Ce comportement est un exemple de retour en arrière catastrophique . Le moteur correspondant de modèle qui met en oeuvre la mise en correspondance regex tente infructueusement toutes les façons possibles que le modèle pourrait correspondre.

Regardons ce que (A+)+B signifie réellement. Superficiellement, il semble dire "un ou plusieurs caractères A suivis d'une valeur B ", mais en réalité, il s'agit d'un ou de plusieurs groupes, chacun composé d'un ou plusieurs caractères A Donc, par exemple:

  • "AB" correspond à un sens seulement: "(A) B"
  • "AAB" correspond à deux manières: "(AA) B" ou "(A) (A) B"
  • "AAAB" correspond à quatre méthodes: "(AAA) B" ou "(AA) (A) B or '(A)(AA)B ou "(A) (A) (A) B"
  • etc

En d'autres termes, le nombre de correspondances possibles est 2 N où N est le nombre de caractères A

L'exemple ci-dessus est clairement inventé, mais les modèles qui présentent ce type de caractéristiques de performance (c'est-à-dire O(2^N) ou O(N^K) pour un grand K ) apparaissent fréquemment lorsque des expressions régulières mal considérées sont utilisées. Il existe des remèdes standard:

  • Évitez d'imbriquer des motifs répétés dans d'autres motifs répétés.
  • Évitez d'utiliser trop de motifs répétés.
  • Utilisez la répétition sans retour en arrière si nécessaire.
  • N'utilisez pas les expressions rationnelles pour les tâches d'analyse complexes. (Écrivez un analyseur approprié à la place.)

Enfin, méfiez-vous des situations où un utilisateur ou un client API peut fournir une chaîne d'expression régulière présentant des caractéristiques pathologiques. Cela peut entraîner un "déni de service" accidentel ou délibéré.

Les références: