001package algs14; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac DoublingRatio.java 005 * Execution: java DoublingRatio 006 * Dependencies: ThreeSum.java Stopwatch.java StdRandom.java StdOut.java 007 * 008 * 009 * % java DoublingRatio 010 * 512 6.48 011 * 1024 8.30 012 * 2048 7.75 013 * 4096 8.00 014 * 8192 8.05 015 * ... 016 * 017 *************************************************************************/ 018 019public class DoublingRatio { 020 public static double timeTrial(int N) { 021 int MAXVAL = 1000000; 022 int[] a = new int[N]; 023 for (int i = 0; i < N; i++) { 024 a[i] = StdRandom.uniform(-MAXVAL, MAXVAL); 025 } 026 int T = 1; // number of tests 027 double sum = 0; 028 for (int t = 0; t < T; t++) { 029 Stopwatch s = new Stopwatch(); 030 //XOneSum.count (a); 031 //XTwoSum.count (a); 032 ThreeSum.count(a); 033 //XFourSum.count(a); 034 //XTwoSumFast.count (a); 035 //ThreeSumFast.count (a); 036 sum += s.elapsedTime(); 037 } 038 return sum/T; 039 } 040 041 private static final int MIN = 125; 042 private static final int MAX = Integer.MAX_VALUE/2; 043 //private static final int MAX = 32768000; 044 //private static final int MAX = 1024000; 045 //private static final int MAX = 64000; 046 public static void main(String[] args) { 047 double prev = timeTrial(MIN); 048 for (int N = MIN*2; N<=MAX; N += N) { 049 double time = timeTrial(N); 050 StdOut.format("%,13d %10.3f %10.3f\n", N, time, time/prev); 051 prev = time; 052 } 053 } 054} 055