# HG changeset patch # User Christian Urban # Date 1595844168 -3600 # Node ID e66bd5c563eb362e051efd0e32287d58528a1ee4 # Parent 923b946347e6f58f57e7b0ef0dd8c70757dff189 updated diff -r 923b946347e6 -r e66bd5c563eb progs/catastrophic.java --- 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"); - } - } - } -} diff -r 923b946347e6 -r e66bd5c563eb progs/catastrophic.js --- 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) diff -r 923b946347e6 -r e66bd5c563eb progs/catastrophic.py --- 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 diff -r 923b946347e6 -r e66bd5c563eb progs/catastrophic.rb --- 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 diff -r 923b946347e6 -r e66bd5c563eb progs/catastrophic/catastrophic.java --- /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"); + } + } + } +} diff -r 923b946347e6 -r e66bd5c563eb progs/catastrophic/catastrophic.js --- /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) diff -r 923b946347e6 -r e66bd5c563eb progs/catastrophic/catastrophic.py --- /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 diff -r 923b946347e6 -r e66bd5c563eb progs/catastrophic/catastrophic.rb --- /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 diff -r 923b946347e6 -r e66bd5c563eb progs/catastrophic/catastrophic2.py --- /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 diff -r 923b946347e6 -r e66bd5c563eb progs/catastrophic/catastrophic9.java --- /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"); + } + } + } +} diff -r 923b946347e6 -r e66bd5c563eb progs/catastrophic2.py --- 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 diff -r 923b946347e6 -r e66bd5c563eb progs/catastrophic9.java --- 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"); - } - } - } -}