updated
authorChristian Urban <christian dot urban at kcl dot ac dot uk>
Tue, 20 Sep 2016 12:13:11 +0100
changeset 420 25bc57b32efa
parent 419 4110ab35e5d8
child 421 7a04f2c532c1
updated
progs/catastrophic.java
progs/catastrophic.py
progs/catastrophic.rb
--- 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)