--- a/progs/catastrophic.java Mon Jul 27 01:55:05 2020 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,45 +0,0 @@
-// A case of catastrophic backtracking in Java 8
-//-----------------------------------------------
-//
-// regexp: (a*)*b
-// strings: aa....
-//
-// compile: javac catastrophic.java
-// call with: java catastrophic
-//
-// IMPORTANT:
-// Java 9 improved its regex matching engine.
-// This example is now much faster.
-//
-
-import java.util.regex.*;
-
-public class catastrophic {
- public static void main(String[] args) {
-
- //we always run all the tests twice -> to warmup of the JVM
- for (int runs = 0; runs < 2; runs++) {
-
- 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"; }
-
- // Measure the average duration of two calls...
- long start = System.nanoTime();
- for (int i = 0; i < 2; i++) {
- pattern.matcher(input).find();
- }
-
- // Print out time
- System.out.println(length + " " + input + ": "
- + ((System.nanoTime() - start) / 2000000000d)
- + "s");
- }
- }
- }
-}
--- a/progs/catastrophic.js Mon Jul 27 01:55:05 2020 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,28 +0,0 @@
-
-
-
-// A case of catastrophic backtracking in JavaScript/Node.js
-//
-// regex: (a*)*b
-// strings: aa...
-//
-// call with:
-//
-// $> node catastrophic.js 20
-//
-// call with timing as:
-//
-// $> time node catastrophic.js 25
-
-
-const args = process.argv[2]
-
-var str = 'a'.repeat(args);
-
-console.log(str)
-
-var re = /^((a)*)*b$/;
-
-var res = re.test(str);
-
-console.log(res)
--- a/progs/catastrophic.py Mon Jul 27 01:55:05 2020 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,22 +0,0 @@
-#!/usr/bin/env python
-import re
-import sys
-
-# case of catastrophic backtracking in Python
-#
-# regex: (a*)*b
-# strings: aa...a
-#
-# call with timing as:
-#
-# > time ./catastrophic.py 20
-
-# counter n given on the command line
-cn = sys.argv[1]
-
-# calling the matching function
-s = ("a" * int(cn))
-m = re.match('(a*)*b' , s)
-
-print s
-print m
--- a/progs/catastrophic.rb Mon Jul 27 01:55:05 2020 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,35 +0,0 @@
-# A case of catastrophic backtracking in Ruby
-#---------------------------------------------
-# example provided by Daniel Baldwin
-#
-#
-# regex: (a?){n} a{n}
-# strings: aa...
-#
-# run on the command line with:
-#
-# $> ruby catastrophic.rb
-#
-
-nums = (1..1000)
-
-#iterate through the nums 1-1000
-nums.each do |i|
-
- start_time = Time.now
- string = "a" * i
-
- #create a new regular expression based on current value of i
- re_str = "a?" * i + "+" + "a" * i
- re = Regexp.new(re_str)
-
- re.match(string)
-
- #if re.match(string)
- # puts "matched string a * #{i} with regex #{re}"
- #else
- # puts "unmatched string a * #{i} with regex #{re}"
- #end
-
- puts "#{i} %.5f" % (Time.now - start_time)
-end
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/catastrophic/catastrophic.java Mon Jul 27 11:02:48 2020 +0100
@@ -0,0 +1,45 @@
+// A case of catastrophic backtracking in Java 8
+//-----------------------------------------------
+//
+// regexp: (a*)*b
+// strings: aa....
+//
+// compile: javac catastrophic.java
+// call with: java catastrophic
+//
+// IMPORTANT:
+// Java 9 improved its regex matching engine.
+// This example is now much faster.
+//
+
+import java.util.regex.*;
+
+public class catastrophic {
+ public static void main(String[] args) {
+
+ //we always run all the tests twice -> to warmup of the JVM
+ for (int runs = 0; runs < 2; runs++) {
+
+ 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"; }
+
+ // Measure the average duration of two calls...
+ long start = System.nanoTime();
+ for (int i = 0; i < 2; i++) {
+ pattern.matcher(input).find();
+ }
+
+ // Print out time
+ System.out.println(length + " " + input + ": "
+ + ((System.nanoTime() - start) / 2000000000d)
+ + "s");
+ }
+ }
+ }
+}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/catastrophic/catastrophic.js Mon Jul 27 11:02:48 2020 +0100
@@ -0,0 +1,28 @@
+
+
+
+// A case of catastrophic backtracking in JavaScript/Node.js
+//
+// regex: (a*)*b
+// strings: aa...
+//
+// call with:
+//
+// $> node catastrophic.js 20
+//
+// call with timing as:
+//
+// $> time node catastrophic.js 25
+
+
+const args = process.argv[2]
+
+var str = 'a'.repeat(args);
+
+console.log(str)
+
+var re = /^((a)*)*b$/;
+
+var res = re.test(str);
+
+console.log(res)
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/catastrophic/catastrophic.py Mon Jul 27 11:02:48 2020 +0100
@@ -0,0 +1,22 @@
+#!/usr/bin/env python
+import re
+import sys
+
+# case of catastrophic backtracking in Python
+#
+# regex: (a*)*b
+# strings: aa...a
+#
+# call with timing as:
+#
+# > time ./catastrophic.py 20
+
+# counter n given on the command line
+cn = sys.argv[1]
+
+# calling the matching function
+s = ("a" * int(cn))
+m = re.match('(a*)*b' , s)
+
+print s
+print m
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/catastrophic/catastrophic.rb Mon Jul 27 11:02:48 2020 +0100
@@ -0,0 +1,35 @@
+# A case of catastrophic backtracking in Ruby
+#---------------------------------------------
+# example provided by Daniel Baldwin
+#
+#
+# regex: (a?){n} a{n}
+# strings: aa...
+#
+# run on the command line with:
+#
+# $> ruby catastrophic.rb
+#
+
+nums = (1..1000)
+
+#iterate through the nums 1-1000
+nums.each do |i|
+
+ start_time = Time.now
+ string = "a" * i
+
+ #create a new regular expression based on current value of i
+ re_str = "a?" * i + "+" + "a" * i
+ re = Regexp.new(re_str)
+
+ re.match(string)
+
+ #if re.match(string)
+ # puts "matched string a * #{i} with regex #{re}"
+ #else
+ # puts "unmatched string a * #{i} with regex #{re}"
+ #end
+
+ puts "#{i} %.5f" % (Time.now - start_time)
+end
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/catastrophic/catastrophic2.py Mon Jul 27 11:02:48 2020 +0100
@@ -0,0 +1,21 @@
+#!/usr/bin/env python
+import re
+import sys
+
+# case of catastrophic backtracking in Python
+#
+# regex: (a*)*b
+# strings: aa...a
+#
+# call with timing as:
+#
+# > time ./catastrophic.py 20
+
+# counter n given on the command line
+cn = sys.argv[1]
+
+# calling the matching function
+s = ("a" * int(cn))
+m = re.match('(a*)*b' , s)
+
+print s
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/catastrophic/catastrophic9.java Mon Jul 27 11:02:48 2020 +0100
@@ -0,0 +1,48 @@
+// A case of catastrophic backtracking in Java 9+
+//------------------------------------------------
+//
+// It is actually not too bad in comparison what Python
+// and Java 8 are to compute. But it is still pretty
+// bad, even in Java 9, considering that the the basic
+// part of the CW improves on this by a factor of 100
+// (...if implemented correctly).
+//
+// regexp: (a*)*b
+// strings: aa....aaa
+//
+// compile with: javac catastrophic9.java
+// call with: java catastrophic9
+//
+//
+
+import java.util.regex.*;
+
+public class catastrophic9 {
+ public static void main(String[] args) {
+
+ //we always run all the tests twice -> to warmup of the JVM
+ for (int runs = 0; runs < 2; runs++) {
+
+ Pattern pattern = Pattern.compile("(a*)*b");
+
+ // Run from 0 to 50000 characters
+ for (int length = 0; length < 50000; length += 5000) {
+
+ // Build input of specified length
+ String input = "";
+ for (int i = 0; i < length; i++) { input += "a"; }
+
+ // Measure the average duration of two calls...
+ long start = System.nanoTime();
+ for (int i = 0; i < 2; i++) {
+ pattern.matcher(input).find();
+ }
+
+ // Print out time
+ System.out.println(length + " a's : "
+ + ((System.nanoTime() - start) / 2000000000d)
+ + " secs");
+ }
+ }
+ }
+}
--- a/progs/catastrophic2.py Mon Jul 27 01:55:05 2020 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,21 +0,0 @@
-#!/usr/bin/env python
-import re
-import sys
-
-# case of catastrophic backtracking in Python
-#
-# regex: (a*)*b
-# strings: aa...a
-#
-# call with timing as:
-#
-# > time ./catastrophic.py 20
-
-# counter n given on the command line
-cn = sys.argv[1]
-
-# calling the matching function
-s = ("a" * int(cn))
-m = re.match('(a*)*b' , s)
-
-print s
--- a/progs/catastrophic9.java Mon Jul 27 01:55:05 2020 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,48 +0,0 @@
-// A case of catastrophic backtracking in Java 9+
-//------------------------------------------------
-//
-// It is actually not too bad in comparison what Python
-// and Java 8 are to compute. But it is still pretty
-// bad, even in Java 9, considering that the the basic
-// part of the CW improves on this by a factor of 100
-// (...if implemented correctly).
-//
-// regexp: (a*)*b
-// strings: aa....aaa
-//
-// compile with: javac catastrophic9.java
-// call with: java catastrophic9
-//
-//
-
-import java.util.regex.*;
-
-public class catastrophic9 {
- public static void main(String[] args) {
-
- //we always run all the tests twice -> to warmup of the JVM
- for (int runs = 0; runs < 2; runs++) {
-
- Pattern pattern = Pattern.compile("(a*)*b");
-
- // Run from 0 to 50000 characters
- for (int length = 0; length < 50000; length += 5000) {
-
- // Build input of specified length
- String input = "";
- for (int i = 0; i < length; i++) { input += "a"; }
-
- // Measure the average duration of two calls...
- long start = System.nanoTime();
- for (int i = 0; i < 2; i++) {
- pattern.matcher(input).find();
- }
-
- // Print out time
- System.out.println(length + " a's : "
- + ((System.nanoTime() - start) / 2000000000d)
- + " secs");
- }
- }
- }
-}