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