--- a/progs/catastrophic.java Wed Sep 14 16:51:04 2016 +0100
+++ b/progs/catastrophic.java Tue Sep 20 12:13:11 2016 +0100
@@ -1,14 +1,21 @@
+// a case of catastrophic backtracking in Java
+//
+// regexp: (a*)*b
+// strings: aa....
+
import java.util.regex.*;
public class catastrophic {
public static void main(String[] args) {
+
+ //we always run all the tests twice -> warmup of the JVM
for (int runs = 0; runs < 2; runs++) {
- //Pattern pattern = Pattern.compile("(0*)*A");
- //Pattern pattern = Pattern.compile("a?{20}a{20}");
-
- // Run from 5 to 25 characters
- for (int length = 5; length < 30; length++) {
- Pattern pattern = Pattern.compile("(a*)*b");
+
+ Pattern pattern = Pattern.compile("(a*)*b");
+
+ // Run from 5 to 28 characters
+ for (int length = 5; length < 28; length++) {
+
// Build input of specified length
String input = "";
for (int i = 0; i < length; i++) { input += "a"; }
@@ -18,10 +25,11 @@
for (int i = 0; i < 2; i++) {
pattern.matcher(input).find();
}
+
System.out.println(length + " " + input + ": "
+ ((System.nanoTime() - start) / 2000000000d)
+ "s");
}
}
}
-}
\ No newline at end of file
+}
--- a/progs/catastrophic.py Wed Sep 14 16:51:04 2016 +0100
+++ b/progs/catastrophic.py Tue Sep 20 12:13:11 2016 +0100
@@ -2,11 +2,23 @@
import re
import sys
+# case of catastrophic backtracking in Python
+#
+# regex: (a?){n} a{n}
+# strings: aa...
+#
+# call with timing as:
+#
+# > time ./catastrophic.py 20
+
+# counter n given on the command line
cn = sys.argv[1]
+# constructing the regex
r1 = '((a?){%s})' % cn
r2 = 'a{%s}' % cn
+# calling the matching function
m = re.match(r1 + r2 , "a" * int(cn))
print m.group(0)
--- a/progs/catastrophic.rb Wed Sep 14 16:51:04 2016 +0100
+++ b/progs/catastrophic.rb Tue Sep 20 12:13:11 2016 +0100
@@ -1,4 +1,4 @@
-# provided by Daniel Baldwin
+# example provided by Daniel Baldwin
nums = (1..1000)