Question sur Java et RegEx

Je dois résoudre le problème suivant :

Soit le texte « abababababababababababababbaaaaabbbbababababababab » ; en prenant les n premiers caractères de ce texte, calculez le temps utilisé par Java pour vérifier une concordance avec l’expression régulière « (a*b*)*c ». Complétez le tableau :

n Temps de traitement (approximatif)
1
10
20
30
40
50
Pour réaliser ce travail, vous pouvez modifier le programme Motif.java pour calculer le temps écoulé. Pour un exemple de ce type de calcul, consultez le fichier Regex.java.

Indice : Pour n=50, le temps de calcul devrait être important.

Le code que je dois utiliser :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

import java.util.regex.*;     public class Motif { public static void main(String[] args) { Pattern RegexCompile = Pattern.compile(args[0]); System.out.println(RegexCompile.matcher(args[1]).matches()); } }

---

Pouvez-vous m'éclaircir svp?

Merci beaucoup!

Salut,

Ce que je comprends, c'est que tu dois réaliser une série de matcher.matches( chaine ), avec une chaine qui fait d'abord 1 caractère, puis 2, puis 3..etc.. (ou 1, puis 10, puis 20 peut-être bien, selon le résultat que tu dois obtenir). Pour chaque série tu dois relever le temps de traitement approximatif

Donc en gros, tu boucles sur i (i de 1 à n) : tu prends i caractères dans args[1] (qui doit au moins les contenir). tu relèves le compteur de nanosecondes (System.nanoTime()) , tu testes le match avec la regex, tu relèves le compteur de nanosecondes et tu fais la différence avec le compteur relevé précédemment : tu as le temps d'éxécution approximatif en ns.

Merci beaucoup pour l'aide mais comme ce n'est pas un cours de programmation j'ai du mal à comprendre.
Le prof dit que l'on peut se servir du fichier suivant pour se baser sur le type de calcul à faire :

Code:

---

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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

import java.util.regex.*;   import java.io.*;       public class Regex {     public static void main(String[] args) {   boolean verbose = false; int pos = 0;   if(args[pos].equals("-v")) {   verbose = true; ++pos;   System.out.println("Mode verbose"); }   if(verbose) System.out.println("Expression régulières: "+args[pos]);   Pattern RegexCompile = Pattern.compile(args[pos]); ++pos;   long debut = System.currentTimeMillis(); for(; pos < args.length ; ++pos) {   try { if(verbose) System.out.println("Je traite le fichier: "+args[pos]);   match(new File(args[pos]),RegexCompile, verbose);   if(verbose) System.out.println("J'ai traité le fichier: "+args[pos]); } catch (IOException ioe) { System.out.println("Impossible de traiter le fichier: "+args[pos]);   ioe.printStackTrace(); } } long fin = System.currentTimeMillis();   System.out.println("Temps écoulé: "+ ((fin-debut)/1000.0)+" s"); }     public static void match(File f, Pattern RegexCompile, boolean verbose) throws IOException {   if(!f.isFile()) return; BufferedReader br = new BufferedReader(new FileReader(f)); try {   String ligne; boolean trouve = false; while((ligne = br.readLine()) != null) {   Matcher m = RegexCompile.matcher(ligne); while( m.find() ) { trouve = true;   System.out.println(f.getPath()+": "+m.group(m.groupCount())); } } if(verbose && !trouve)   System.out.println("Le motif n'a pas été trouvé!"); } finally { br.close(); } } }

---

Quand j'execute le programme : java Regex "(a*b*)*c" "abababababababababababababbaaaaabbbbababababababab ", j'obtiens toujours 0,00sec en temps écoulé même si le temps de calcul est très long.

Citation:

---

Envoyé par lsebe2

Quand j'execute le programme : java Regex "(a*b*)*c" "abababababababababababababbaaaaabbbbababababababab ", j'obtiens toujours 0,00sec en temps écoulé.

Que dois-je changer dans le code exactement?

---

Avec un temps chronométré en millisecondes çà ne m'étonne pas (il faut des chaines très longues avant d'atteindre un temps mesurable). Essaye avec nanoTime() au lieu de currentTimeMillis(). (En plus le programme que tu donnes affiche le temps en secondes - tout dépend ce que tu appelles très long), par contre, il n'a pas grand chose avoir avec le sujet de ta première question, puisqu'il va lire des fichiers.

Citation:

---

Il faut des chaines très longues avant d'atteindre un temps mesurable

---

Avec une telle pattern et une telle chaîne, il ne manque que quelques caractères pour que ça se compte en siècles.

Citation:

---

Envoyé par CosmoKnacki

Avec une telle pattern et une telle chaîne, il ne manque que quelque caractères pour que ça se compte en siècles.

---

J'ai peut-être un peu sous-estimé le temps de traitement, mais d'après les mesures que j'obtiens, j'ai l'impression qu'il faut plus que "quelques" caractères avant d'atteindre le siècle :

Nombre de caractères	Temps (s)	Temps n/Temps n-1
1	0.001	-
2	0.002	2.0
3	0.0	0.0
4	0.001
5	0.0	0.0
6	0.0
7	0.001
8	0.0	0.0
9	0.001
10	0.0	0.0
11	0.001
12	0.001	1.0
13	0.001	1.0
14	0.001	1.0
15	0.001	1.0
16	0.0	0.0
17	0.001
18	0.001	1.0
19	0.001	1.0
20	0.001	1.0
21	0.002	2.0
22	0.003	1.5
23	0.004	1.3333333333333333
24	0.005	1.25
25	0.007	1.4
26	0.011	1.5714285714285714
27	0.017	1.5454545454545454
28	0.024	1.411764705882353
29	0.04	1.6666666666666667
30	0.067	1.675
31	0.122	1.8208955223880596
32	0.244	2.0
33	0.42	1.721311475409836
34	0.864	2.057142857142857
35	1.607	1.8599537037037037
36	3.075	1.913503422526447
37	4.987	1.621788617886179
38	8.167	1.6376579105674753
39	11.945	1.4625933635361823
40	19.025	1.5927166178317287
41	26.143	1.3741392904073588
42	39.258	1.5016639253337414
43	54.157	1.379515003311427
44	79.927	1.4758387650719205
45	110.44	1.3817608567818134
46	161.754	1.4646323795726186
47	223.068	1.3790570866871916
48	322.806	1.447119264080908
49	446.863	1.384308222275918
50	822.009	1.8395100959354433

C'est parce que tu utilises la méthode matches qui est ancrée, mais l'énoncé demande de trouver une concordance, pas si toute la chaîne correspond, donc je pense qu'il faut plutôt faire le test avec la méthode find.

D'après moi l'objectif du TP est d'illustrer la complexité exponentielle de ce genre de pattern en cas d'échec.

nb caractères	chaîne	temps (s)
1	a	0.000
10	ababababab	0.002
20	abababababababababab	0.005
30	abababababababababababababbaaa	0.105
40	abababababababababababababbaaaaabbbbabab	9.088
50	abababababababababababababbaaaaabbbbababababababab	315.719

J'avais traduit en effet "concordance" par "matches".