Le blog de fx: Expressions régulières en Java, greedy quantifier, reluctant quantifier et performances

Les expressions régulières sont très pratiques pour analyser ou filtrer des chaines de caractères. Un exemple type est de repérer tous les tags html présents dans une chaine de caractères. L'expression régulière la plus simple à laquelle on peut penser pour ça est :
<.*>

Maintenant un petit programme java pour tester :

String stringToAnalyze = "<html><head><title>Title</title></head><body>The body</body></html>";
Pattern pattern = Pattern.compile("<.*>");
Matcher matcher = pattern.matcher(stringToAnalyze);
while (matcher.find()) { 
   System.out.println(matcher.group());
}

Problème, en sortie je récupère le résultat suivant :

<html><head><title>Title</title></head><body>The body</body></html>

En fait l'expression régulière va essayer de matcher la chaîne de caractères la plus grande possible (* est ce qu'on appelle un "greedy quantifyer"), ici ce sera toute ma chaîne initiale. Pour éviter ça, deux solutions :

Préciser que la chaîne ne doit pas contenir le caractère '<'. L'expression devient : <[^>]*>
Utiliser un "reluctant quantifier" à la place du "greedy quantifier pour rechercher cette fois-ci la chaîne la plus courte possible. L'expression devient : <.*?>

Dans les deux cas, j'obtiens le résultat attendu :

<html>
<head>
<title>
</title>
</head>
<body>
</body>
</html>

Laquelle de ces deux solutions est la plus performante ? Personnellement, je parierais sur la deuxième qui me parait plus concise et naturelle donc devrait permettre au compilateur de bien optimiser.

Faisons un petit test Junit pour comparer :

public class RegexPerfTest extends TestCase {

 private static final int nbOfIterations = 10000;
 private static String HTML = "<html><head><title>Title</title></head><body>The body</body></html>";
 static {
  // Build a big html string to test
  for (int i = 0; i < 10; i++) {
   HTML += HTML;
  }
 }

 public void testGreedyQuantifier() throws Exception {
  testPattern("<[^>]*>");
 }

 public void testReluctantQuantifier() throws Exception {
  testPattern("<.*?>");
 }

 public void testPattern(String patternString) throws Exception {
  Pattern pattern = Pattern.compile(patternString);
  for (int i = 0; i < nbOfIterations; i++) {
   Matcher matcher = pattern.matcher(HTML);
   while (matcher.find()) {
    // Do nothing
   }
  }
 }