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"); - } - } - } -}