001package algs14; 002import stdlib.*; 003public class XCountingString { 004 // Test variants that resize additively or multiplicatively 005 // int capacity = 1 + a.length; 006 // int capacity = 2 * a.length; 007 // int capacity = (int)Math.ceil(1.5 * a.length); 008 private static char[] resize (char[] a) { 009 int capacity = 2 * a.length; 010 char[] result = new char[capacity]; 011 for (int i = 0; i < a.length; i = i + 1) { 012 result[i] = a[i]; 013 numOps = numOps + 1; 014 } 015 return result; 016 } 017 // f creates a string of length N, counting the total size of all strings created 018 public static String f (long N) { 019 char[] a = new char[1]; 020 for (int i = 0; i < N; i = i + 1) { 021 if (i >= a.length) 022 a = resize(a); 023 a[i] = '*'; 024 numOps = numOps + 1; 025 } 026 return String.valueOf(a); // creates a string in linear time 027 } 028 private static long numOps; 029 public static void main (String[] args) { 030 long MIN = 500L; 031 long MAX = 3200000L; 032 Stopwatch sw = new Stopwatch (); 033 numOps = 0; 034 f(MIN); 035 double prevCount = numOps; 036 double prevTime = sw.elapsedTime (); 037 for (long N = MIN*2; N <= MAX; N=N*2) { 038 sw = new Stopwatch (); 039 numOps = 0; 040 f(N); 041 long count = numOps; 042 double time = sw.elapsedTime (); 043 StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f [%10.3f : %10.3f]\n", N, count, count / prevCount, time, time/prevTime); 044 //StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f\n", N, count, count / prevCount); 045 prevCount = count; 046 prevTime = time; 047 } 048 } 049}