# HG changeset patch # User Christian Urban # Date 1474369991 -3600 # Node ID 25bc57b32efa0eaf077a472e497b82636d91647c # Parent 4110ab35e5d8e2ef20f71cd6d50f6df27b56fd0e updated diff -r 4110ab35e5d8 -r 25bc57b32efa progs/catastrophic.java --- 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 +} diff -r 4110ab35e5d8 -r 25bc57b32efa progs/catastrophic.py --- 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) diff -r 4110ab35e5d8 -r 25bc57b32efa progs/catastrophic.rb --- 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)