Discussion :

[NicoV]

Bonjour,

J'ai un énorme problème de performance avec une expression régulière dans de très rares cas. Quelqu'un pourrait-il m'aider à améliorer ces performances ?

L'exemple ci-dessus présente un texte qui est parsé assez rapidement (pas de match trouvé, c'est normal), mais quand j'ajoute des caractères par exemple au début de "général", le temps d'exécution augmente de façon exponentielle :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
  public static void main(String[] args) {
    Pattern pattern = Pattern.compile("\\{\\{(\\s*[lL]\\Qoupe\\E\\s*(?:\\|((?:(?:[^\\{\\}]*)|(?:\\{\\{\\!\\}\\}))*))?)\\}\\}");
    Matcher matcher = pattern.matcher("{{loupe|c=U [[général]] fut {{rom|II|2}}de .}} [[Lozère]]");
    long begin = System.currentTimeMillis();
    while (matcher.find()) {
      System.out.println("Found: " + matcher.start() + "," + matcher.end());
    }
    long end = System.currentTimeMillis();
    System.out.println("Done in " + (end - begin) + "ms");
  }

• chaine initiale: 797ms
• 1 caractère supplémentaire: 1797ms
• 2 caractères supplémentaires: 3515ms
• 3 caractères supplémentaires: 6984ms
• 4 caractères supplémentaires: 13922ms
• 5 caractères supplémentaires: 27813ms
• 6 caractères supplémentaires: 55672ms

... en gros, 1 caractère de plus = 2 fois plus de temps

Explications du pattern

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

"\\{\\{(\\s*[lL]\\Qoupe\\E\\s*(?:\\|((?:(?:[^\\{\\}]*)|(?:\\{\\{\\!\\}\\}))*))?)\\}\\}"

Ce que j'essaye de faire, c'est trouver les chaînes de caractères qui respectent tous les critères suivants :
* commencent par {{
* puis un nombre quelconque de caractères blancs
* puis un texte donné, la première lettre pouvant être en majuscules ou minuscules (dans l'exemple, c'est loupe ou Loupe)
* puis un nombre quelconque de caractères blancs
* puis un nombre quelconque de paramètres séparés par des | (les paramètres ne devant pas contenir de { ou de } sauf si c'est {{!}}). Quand j'ai trouvé le texte, j'ai besoin d'avoir la valeur des paramètres.
* finissent par }}

Voilà, toute aide est la bienvenue

Nico

[dingoth]

Tiens... un analyseur de sources Wikipédia

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
String pipe = Pattern.quote("|");
String wpPipe = Pattern.quote("{{!}}");
String accoL = Pattern.quote("{{");
String accoR = Pattern.quote("}}");
String forbiddenParam = Pattern.quote("{}|");
String template = "\\s*\\p{L}\\p{Ll}*\\s*"; // caractères unicodes autorisés, comme É, par exemple
String param = pipe + "(?:[^"+forbiddenParam+"]+|"+wpPipe+")+"; // construction d'un paramètre : tout caractère sauf {, } et |.
String regex = accoR + template + "("+param+")*" + accoL;

Bon, c'est pas super au niveau unicode (alors que WP en utilise à fond), mais ça devrait fonctionner (non testé).

En revanche, je crois que ton application serait plus efficace en créant un analyseur toi-même et en utilisant de simples états (dans modèle, dans paramètre de modèle, dans lien, etc.)

[NicoV]

Oui, c'est bien pour du Wikipédia :
http://fr.wikipedia.org/wiki/Utilisa.../Documentation

Je vais essayer dans un premier temps ton pattern pour voir si mes problèmes de performance se règlent, et c'est vrai que dans un deuxième temps, faire mon propre parseur pourrait se révéler plus efficace mais çà fait quand même pas mal de boulot. Les simples états ne sont à priori pas suffisants, dans l'exemple qui me pose problème, il y a par exemple des modèles faisant partie de paramètres de modèles, ...

Merci

[Alkhan]

Bonjour,

Pour ce qui est des regexp je ne connais pas bien, mais quand j'ai besoin de faire ce que tu veux faire, en général j'utilise un StringTokenizer ! Et c'est plutôt performant.

[NicoV]

Bonjour,

De mon côté je ne connais pas trop StringTokenizer, mais à première vue, çà ne me semblait pas assez puissant pour les critères dont j'ai besoin. Comment ferais-tu avec un StringTokenizer pour récuper les chaînes de caractères qui respectent les critères que j'ai indiqué ?

[dingoth]

StringTokenizer n'est utile dans ce cas qu'avec une machine à état, pour savoir quoi chercher quand il le faut.

D'ailleurs, je ne l'utilise que très rarement, vu la documentation :

StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead.

[Alkhan]

avec les regex je n'ai jamais vu quelque chose de performant (mais je les ai utilisé que très peux) !
Avec StringTokenizer tu peux lui donner plusieurs séparateurs et faire en sorte qu'il te renvoi les séparateurs comme des tokens, ce qui te permet de savoir ou tu en ai dans tes tokens !!

Je dis pas que c'est la meilleur solution mais je l'utilise et en général les perfs sont acceptable

[NicoV]

Pour les perfs des regexp, en règle général, c'est tout à fait acceptable pour l'application que je fais: j'ai analysé des milliers de pages de Wikipédia avec la regexp du premier post et çà va, mais voilà pour une page de temps en temps on passe dans une autre dimension. Avec l'exemple que j'ai mis, en rajoutant 6 caractères on passe de 1s à 1mn alors que la page existante fait en fait plusieurs milliers de caractères supplémentaires ( http://fr.wikipedia.org/wiki/Paysann...tion_française )

Je vais faire quelques tests avec les regexp, mais sinon je passerai à mon propre analyseur syntaxique qui sera beaucoup plus efficace, mais aussi beaucoup plus long et compliqué à coder.

[dingoth]

As-tu regardé le logiciel WikiMedia ? histoire de voir comment ça fonctionne en interne. Tu pourrais sans doute reprendre leur méthode et l'adapter à Java, non ?

[dingoth]

bon, finalement, j'ai compris d'où vient ton problème. De là à le résoudre...

En fait, tu n'utilises que des regex gloutonnes. Tu devrais tenter de voir les regex pas-gloutonnes (je connais pas le nom, désolé). Elles sont de la forme : "test(.*?)test". Elles permettent de chercher la plus petite chaîne de caractère correspondant à la regex.

Par exemple : en testant test(.*?)test sur "testabctestcbatest", tu obtiendras deux occurences : "abc" et "cba". Alors qu'avec la méthode traditionnelle, tu n'en retires que "abctestcba".

Il faut l'adapter à ta regex à présent. Et là, c'est pas coton

[NicoV]

Je crois que je vais essayer ta suggestion d'analyser le code de MediaWiki pour voir si je peux en tirer quelque chose comme base de mon code Java. (EDIT: plus tard vu le résultat en-dessous)

Pour les regex gloutonnes, çà m'a donné une bonne piste. Il faut que je vérifie que j'obtiens les mêmes résultats, mais en remplaçant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

"\\{\\{(loupe(?:\\|((?:(?:[^\\{\\}]*)|(?:\\{\\{\\!\\}\\}))*))?)\\}\\}"

par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

"\\{\\{(loupe(?:\\|((?:(?:[^\\{\\}])|(?:\\{\\{\\!\\}\\}))*))?)\\}\\}"

soit une regex gloutonne de moins, je passe de 1 mn à 0 ms avec les 6 caractères supplémentaires

Explication du changement : çà concerne les critères pour la partie des paramètres du modèle
- avant: un nombre quelconque de ((un nombre quelconque de (caractères hors { et })) OU ({{!}}))
- après: un nombre quelconque de ((caractères hors { et }) OU ({{!}}))

Merci beaucoup


EDIT: et sur la page qui me posait problème avant (temps infini), çà a l'air instantané maintenant