001// Exercise 1.4.31 002package algs14; 003import stdlib.*; 004import java.util.NoSuchElementException; 005import algs13.ResizingArrayStack; 006 007/* 008Here is the kind of output I get before fixing the move method. 009 010 4000 0.4 3.1 011 8000 1.5 4.1 012 16000 4.9 3.2 013 32000 21.6 4.4 014 015Here is the kind of output I get after fixing the move method. 016You can see that it is much faster, but not very consistent. 017This is due to garbage collection and other system effects. 018 019 4000 0.0 0.7 020 8000 0.0 1.2 021 16000 0.0 2.2 022 32000 0.0 0.2 023 64000 0.0 1.5 024 128000 0.0 5.7 025 256000 0.1 5.3 026 512000 0.2 2.1 027 1024000 0.4 1.9 028 2048000 0.7 2.0 029 4096000 2.5 3.6 030 031 4000 0.0 0.8 032 8000 0.0 1.6 033 16000 0.0 1.8 034 32000 0.0 0.1 035 64000 0.0 2.0 036 128000 0.0 4.5 037 256000 0.1 5.7 038 512000 0.2 1.8 039 1024000 0.3 1.8 040 2048000 0.7 2.1 041 4096000 3.7 5.1 042 043 044 4000 0.0 0.7 045 8000 0.0 2.0 046 16000 0.0 1.9 047 32000 0.0 0.2 048 64000 0.0 1.7 049 128000 0.0 4.4 050 256000 0.0 1.6 051 512000 0.1 2.3 052 1024000 0.1 0.6 053 2048000 0.1 2.0 054 4096000 0.2 2.4 055 */ 056 057public class MyDequeUsingStacks<T> { 058 ResizingArrayStack<T> sl = new ResizingArrayStack<>(); 059 ResizingArrayStack<T> sr = new ResizingArrayStack<>(); 060 public boolean isEmpty () { return sl.isEmpty() && sr.isEmpty(); } 061 public int size () { return sl.size() + sr.size(); } 062 public void pushLeft (T item) { sl.push (item); } 063 public void pushRight (T item) { sr.push (item); } 064 065 private void move (ResizingArrayStack<T> from, ResizingArrayStack<T> to) { 066 if (!to.isEmpty ()) throw new IllegalArgumentException(); 067 if (from.isEmpty ()) throw new IllegalArgumentException(); 068 while (!from.isEmpty ()) { 069 to.push(from.pop()); 070 } 071 // TODO: 072 // Run the main method below. 073 // Note that the execution is correct (that's the first part of the test). 074 // Note also that performance is terrible (that's the second part of the test). 075 // In particular, for N pops, the running time increases proportionally to N^2. 076 // So the amortized time for each pop is linear (proportional to N). 077 // 078 // Your goal is to change this method so that overall performance of 079 // the main method improves, by altering the number of elements moved 080 // from "from" to "to". 081 // 082 // Your solution must continue to pass the correctness tests below. 083 // It must also have amortized constant time per pop. 084 // So for N pops, the running time should increase proportionally to N. 085 // 086 // You can use one temporary stack to help you: 087 // ResizingArrayStack<T> tmp = new ResizingArrayStack<>(); 088 // You may find it helpful to print the sizes while debugging: 089 // StdOut.println ("from: " + from.size () + " to: " + to.size ()); 090 // You can print out the content of the stacks by uncommenting the 091 // lines in popLeft and popRight, below. 092 } 093 094 public T popLeft () { 095 if (isEmpty()) { throw new NoSuchElementException(); } 096 if (sl.isEmpty ()) { 097 //StdOut.println("r2l before: " + sl + ": " + sr); 098 move (sr, sl); 099 //StdOut.println("r2l after: " + sl + ": " + sr); 100 } 101 return sl.pop (); 102 } 103 104 public T popRight () { 105 if (isEmpty()) { throw new NoSuchElementException(); } 106 if (sr.isEmpty ()) { 107 //StdOut.println("l2r before: " + sl + ": " + sr); 108 move (sl, sr); 109 //StdOut.println("l2r after: " + sl + ": " + sr); 110 } 111 return sr.pop (); 112 } 113 114 public String toString () { 115 if (isEmpty ()) return "[ ]"; 116 117 ResizingArrayStack<T> srBackwards = new ResizingArrayStack<>(); 118 for (T item : sr) 119 srBackwards.push (item); 120 121 StringBuilder sb = new StringBuilder ("[ "); 122 for (T item : sl) { 123 sb.append (item); 124 sb.append (" "); 125 } 126 for (T item : srBackwards) { 127 sb.append (item); 128 sb.append (" "); 129 } 130 131 sb.append ("]"); 132 return sb.toString (); 133 } 134 private void check (String expected) { 135 if (expected != null) { 136 if (!expected.equals (this.toString ())) throw new Error ("Expected \"" + expected + "\", got \"" + this + "\""); 137 } 138 //StdOut.println (this); 139 } 140 private void check (T iExpected, T iActual, String expected) { 141 if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\""); 142 check (expected); 143 } 144 private void check (T iExpected, T iActual) { 145 if (!iExpected.equals (iActual)) throw new Error ("Expected \"" + iExpected + "\", got \"" + iActual + "\""); 146 } 147 private static void correctnessTest () { 148 MyDequeUsingStacks<Integer> d1 = new MyDequeUsingStacks<> (); 149 d1.pushLeft(0); 150 d1.pushLeft(1); 151 d1.pushLeft(2); 152 d1.pushLeft(3); 153 d1.check(0,d1.popRight()); 154 d1.check(3,d1.popLeft()); 155 d1.check(1,d1.popRight()); 156 d1.check(2,d1.popLeft()); 157 d1.pushRight(0); 158 d1.pushRight(1); 159 d1.pushRight(2); 160 d1.pushRight(3); 161 d1.check(0,d1.popLeft()); 162 d1.check(3,d1.popRight()); 163 d1.check(1,d1.popLeft()); 164 d1.check(2,d1.popRight()); 165 166 Integer k; 167 168 if (!d1.isEmpty ()) throw new Error(); 169 d1.pushLeft (11); 170 d1.check ("[ 11 ]"); 171 d1.pushLeft (12); 172 d1.check ("[ 12 11 ]"); 173 k = d1.popLeft (); 174 d1.check (12, k, "[ 11 ]"); 175 k = d1.popLeft (); 176 d1.check (11, k, "[ ]"); 177 178 try { 179 d1.popLeft (); 180 throw new Error ("Expected exception"); 181 } catch (NoSuchElementException e) {} 182 183 if (!d1.isEmpty ()) throw new Error(); 184 for (int i = 0; i < 20; i++) { d1.pushLeft (i); } 185 for (int i = 0; i < 20; i++) { d1.check (19-i, d1.popLeft ()); } 186 187 if (!d1.isEmpty ()) throw new Error(); 188 for (int i = 0; i < 20; i++) { d1.pushLeft (i); } 189 for (int i = 0; i < 20; i++) { d1.check (i, d1.popRight ()); } 190 191 if (!d1.isEmpty ()) throw new Error(); 192 for (int i = 0; i < 20; i++) { d1.pushLeft (i); } 193 for (int i = 0; i < 10; i++) { d1.check (i, d1.popRight ()); } 194 for (int i = 0; i < 10; i++) { d1.check (19-i, d1.popLeft ()); } 195 196 if (!d1.isEmpty ()) throw new Error(); 197 for (int i = 0; i < 20; i++) { d1.pushLeft (i); } 198 for (int i = 0; i < 10; i++) { d1.check (19-i, d1.popLeft ()); } 199 for (int i = 0; i < 10; i++) { d1.check (i, d1.popRight ()); } 200 201 if (!d1.isEmpty ()) throw new Error(); 202 d1.pushRight (11); 203 d1.check ("[ 11 ]"); 204 d1.pushRight (12); 205 d1.check ("[ 11 12 ]"); 206 k = d1.popRight (); 207 d1.check (12, k, "[ 11 ]"); 208 k = d1.popRight (); 209 d1.check (11, k, "[ ]"); 210 211 if (!d1.isEmpty ()) throw new Error(); 212 for (int i = 0; i < 20; i++) { d1.pushRight (i); } 213 for (int i = 0; i < 20; i++) { d1.check (19-i, d1.popRight ()); } 214 215 if (!d1.isEmpty ()) throw new Error(); 216 for (int i = 0; i < 20; i++) { d1.pushRight (i); } 217 for (int i = 0; i < 20; i++) { d1.check (i, d1.popLeft ()); } 218 219 if (!d1.isEmpty ()) throw new Error(); 220 for (int i = 0; i < 20; i++) { d1.pushRight (i); } 221 for (int i = 0; i < 10; i++) { d1.check (i, d1.popLeft ()); } 222 for (int i = 0; i < 10; i++) { d1.check (19-i, d1.popRight ()); } 223 224 if (!d1.isEmpty ()) throw new Error(); 225 for (int i = 0; i < 20; i++) { d1.pushRight (i); } 226 for (int i = 0; i < 10; i++) { d1.check (19-i, d1.popRight ()); } 227 for (int i = 0; i < 10; i++) { d1.check (i, d1.popLeft ()); } 228 229 try { 230 d1.popRight (); 231 throw new Error ("Expected exception"); 232 } catch (NoSuchElementException e) {} 233 234 StdOut.println("Finished correctness test."); 235 } 236 237 private static void performanceTest() { 238 int MIN = 2000; 239 int MAX = 4096000; 240 double prev = timeTrial(MIN); 241 for (int N = MIN*2; N<=MAX; N += N) { 242 double time = timeTrial(N); 243 StdOut.format("%8d %9.3f %5.1f\n", N, time, time/prev); 244 prev = time; 245 } 246 } 247 private static double timeTrial(int N) { 248 int NUM_TRIALS = 1; 249 MyDequeUsingStacks<Integer> d1 = new MyDequeUsingStacks<> (); 250 Stopwatch sw = new Stopwatch (); 251 for (int trial=0; trial < NUM_TRIALS; trial++) { 252 for (int i=0; i<2*N; i++) { 253 d1.pushLeft (i); 254 } 255 for (int i=0; i<N; i++) { 256 d1.popRight(); 257 d1.popLeft(); 258 } 259 } 260 return sw.elapsedTime (); 261 } 262 263 264 public static void main (String args[]) { 265 //Trace.drawStepsOfMethod ("correctnessTest"); 266 //Trace.drawStepsOfMethod ("move"); 267 //Trace.run (); 268 correctnessTest (); 269 performanceTest (); 270 } 271}