|
1 // a case of catastrophic backtracking in Java |
|
2 // |
|
3 // regexp: (a*)*b |
|
4 // strings: aa.... |
|
5 |
1 import java.util.regex.*; |
6 import java.util.regex.*; |
2 |
7 |
3 public class catastrophic { |
8 public class catastrophic { |
4 public static void main(String[] args) { |
9 public static void main(String[] args) { |
|
10 |
|
11 //we always run all the tests twice -> warmup of the JVM |
5 for (int runs = 0; runs < 2; runs++) { |
12 for (int runs = 0; runs < 2; runs++) { |
6 //Pattern pattern = Pattern.compile("(0*)*A"); |
13 |
7 //Pattern pattern = Pattern.compile("a?{20}a{20}"); |
14 Pattern pattern = Pattern.compile("(a*)*b"); |
8 |
15 |
9 // Run from 5 to 25 characters |
16 // Run from 5 to 28 characters |
10 for (int length = 5; length < 30; length++) { |
17 for (int length = 5; length < 28; length++) { |
11 Pattern pattern = Pattern.compile("(a*)*b"); |
18 |
12 // Build input of specified length |
19 // Build input of specified length |
13 String input = ""; |
20 String input = ""; |
14 for (int i = 0; i < length; i++) { input += "a"; } |
21 for (int i = 0; i < length; i++) { input += "a"; } |
15 |
22 |
16 // Measure the average duration of two calls... |
23 // Measure the average duration of two calls... |
17 long start = System.nanoTime(); |
24 long start = System.nanoTime(); |
18 for (int i = 0; i < 2; i++) { |
25 for (int i = 0; i < 2; i++) { |
19 pattern.matcher(input).find(); |
26 pattern.matcher(input).find(); |
20 } |
27 } |
|
28 |
21 System.out.println(length + " " + input + ": " |
29 System.out.println(length + " " + input + ": " |
22 + ((System.nanoTime() - start) / 2000000000d) |
30 + ((System.nanoTime() - start) / 2000000000d) |
23 + "s"); |
31 + "s"); |
24 } |
32 } |
25 } |
33 } |