001package algs14; 002import stdlib.*; 003 004public class XPerformanceOfArrays { 005 private double[] a; 006 private int N; 007 public XPerformanceOfArrays() { 008 this.a = new double[1]; 009 this.N = 0; 010 } 011 private void resize(int capacity) { 012 double[] temp = new double[capacity]; 013 for (int i = 0; i < N; i+=1) { 014 if (SHOW) StdOut.format ("%02d ", i); 015 temp[i] = a[i]; 016 ops += 1; 017 } 018 if (SHOW) StdOut.println(); 019 a = temp; 020 } 021 public void push(double item) { 022 if (N == a.length) resize (1+N); //resize((int)Math.ceil (N*1.5)); 023 a[N] = item; 024 N += 1; 025 ops += 1; 026 } 027 028 private static long ops; 029 private static boolean SHOW = true; 030 public static void main(String[] args) { 031 timeTrial(32); 032 SHOW = false; 033 034 int MIN = 256; 035 int MAX = 100_000_000; 036 double prevTime = timeTrial(MIN); 037 double prevOps = ops; 038 double deltaSum = 0; 039 int deltaNum = 0; 040 for (int N = MIN*2; N<=MAX; N += N) { 041 double time = timeTrial(N); 042 StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f [%10.3f : %10.3f]\n", N, ops, ops / prevOps, time, time/prevTime); 043 prevTime = time; 044 deltaSum += ops/prevOps; 045 deltaNum += 1; 046 prevOps = ops; 047 } 048 StdOut.format ("Average delta: %.3f\n", deltaSum/deltaNum); 049 } 050 public static double timeTrial(int N) { 051 ops = 0; 052 Stopwatch s = new Stopwatch(); 053 XPerformanceOfArrays stack = new XPerformanceOfArrays(); 054 for (int j=0; j<N; j+=1) { 055 stack.push (j); 056 } 057 return s.elapsedTime(); 058 } 059}