TimeSorts


1   /*
2    * Copyright (c) 2000-2001 Sosnoski Software Solutions, Inc.
3    *
4    * Permission is hereby granted, free of charge, to any person obtaining a copy
5    * of this software and associated documentation files (the "Software"), to deal
6    * in the Software without restriction, including without limitation the rights
7    * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8    * copies of the Software, and to permit persons to whom the Software is
9    * furnished to do so, subject to the following conditions:
10   *
11   * The above copyright notice and this permission notice shall be included in
12   * all copies or substantial portions of the Software.
13   *
14   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19   * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20   * IN THE SOFTWARE.
21   */
22  
23  import java.util.*;
24  
25  import com.sosnoski.util.array.*;
26  
27  /**
28   * Benchmark to compare the performance of various collections in a test using
29   * simple primitive values. The basic test is a bubble sort algorithm running
30   * on a set of <code>int</code> values. Essentially all the execution time of
31   * each test run is spent in a tight loop comparing and sometimes exchanging
32   * values in the set being sorted. Several variations of the test are
33   * performed, each using a different collection variation.
34   *
35   * @author Dennis M. Sosnoski
36   * @version 1.0
37   */
38  
39  public class TimeSorts
40  {
41      /**
42       * Default count of test passes to be executed.
43       */
44  
45      public static final int DEFAULT_PASS_COUNT = 1;
46  
47      /**
48       * Delay in milliseconds between test passes.
49       */
50  
51      public static final int DELAY_BETWEEN_TESTS = 1000;
52  
53      /**
54       * Time to wait after requesting a garbage collection.
55       */
56  
57      public static final int GARBAGE_COLLECT_DELAY = 1000;
58  
59      /**
60       * Initial size of array for storing values to be sorted.
61       */
62  
63      public static final int INITIAL_COLLECTION_SIZE = 10;
64  
65      /**
66       * Additive constant value for pseudo-random number generator.
67       */
68  
69      public static final int SEQUENCE_ADD = 11;
70  
71      /**
72       * Multiplicative constant value for pseudo-random number generator.
73       */
74  
75      public static final int SEQUENCE_MULTIPLY = 43;
76  
77      /**
78       * Last value in generated pseudo-random value sequence.
79       */
80  
81      private int lastValue;
82  
83      /**
84       * Start time for test run.
85       */
86  
87      private long startTime;
88  
89      /**
90       * Check value for validating test results.
91       */
92  
93      private int checkResult;
94  
95      /**
96       * Flag for printing of test results enabled.
97       */
98  
99      private boolean printFlag;
100 
101     /**
102      * Generates the next value in the pseudo-random sequence used for
103      * controlling the test.
104      *
105      * @return next value in sequence
106      */
107 
108     protected int nextInSequence() {
109         lastValue = (lastValue + SEQUENCE_ADD) * SEQUENCE_MULTIPLY;
110         return lastValue;
111     }
112 
113     /**
114      * Initializes a linear collection with a sequence of pseudo-random values.
115      *
116      * @param count number of data values to be used
117      * @param collect collection to be filled with values from pseudo-random
118      * sequence
119      */
120 
121     public void fillCollection(int count, int[] collect) {
122         for (int i = 0; i < count; i++) {
123             collect[i] = nextInSequence();
124         }
125     }
126 
127     public void fillCollection(int count, DirectIntArray collect) {
128         collect.clear();
129         for (int i = 0; i < count; i++) {
130             collect.add(nextInSequence());
131         }
132     }
133 
134     public void fillCollection(int count, IntArray collect) {
135         collect.clear();
136         for (int i = 0; i < count; i++) {
137             collect.add(nextInSequence());
138         }
139     }
140 
141     public void fillCollection(int count, IntegerArray collect) {
142         collect.clear();
143         for (int i = 0; i < count; i++) {
144             collect.add(new Integer  (nextInSequence()));
145         }
146     }
147 
148     public void fillCollection(int count, ObjectArray collect) {
149         collect.clear();
150         for (int i = 0; i < count; i++) {
151             collect.add(new Integer  (nextInSequence()));
152         }
153     }
154 
155     public void fillCollection(int count, ArrayList collect) {
156         collect.clear();
157         for (int i = 0; i < count; i++) {
158             collect.add(new Integer  (nextInSequence()));
159         }
160     }
161 
162     public void fillCollection(int count, Vector collect) {
163         collect.clear();
164         for (int i = 0; i < count; i++) {
165             collect.addElement(new Integer  (nextInSequence()));
166         }
167     }
168 
169     /**
170      * Runs the sort operation on a linear collection.
171      *
172      * @param count number of data values in collection
173      * @param collect collection of values to be sorted
174      * @return number of exchange operations performed
175      */
176 
177     public int runSort(int count, int[] collect) {
178         int swaps = 0;
179         for (int i = 0; i < count - 1; i++) {
180             int min = collect[i];
181             for (int j = i + 1; j < count; j++) {
182                 if (min > collect[j]) {
183                     int temp = collect[j];
184                     collect[j] = min;
185                     min = temp;
186                     swaps++;
187                 }
188             }
189             collect[i] = min;
190         }
191         return swaps;
192     }
193 
194     public int runSort(int count, DirectIntArray collect) {
195         int swaps = 0;
196         for (int i = 0; i < count - 1; i++) {
197             int min = collect.get(i);
198             for (int j = i + 1; j < count; j++) {
199                 if (min > collect.get(j)) {
200                     int temp = collect.get(j);
201                     collect.set(j, min);
202                     min = temp;
203                     swaps++;
204                 }
205             }
206             collect.set(i, min);
207         }
208         return swaps;
209     }
210 
211     public int runSort(int count, IntArray collect) {
212         int swaps = 0;
213         for (int i = 0; i < count - 1; i++) {
214             int min = collect.get(i);
215             for (int j = i + 1; j < count; j++) {
216                 if (min > collect.get(j)) {
217                     int temp = collect.get(j);
218                     collect.set(j, min);
219                     min = temp;
220                     swaps++;
221                 }
222             }
223             collect.set(i, min);
224         }
225         return swaps;
226     }
227 
228     public int runSort(int count, IntegerArray collect) {
229         int swaps = 0;
230         for (int i = 0; i < count - 1; i++) {
231             Integer   min = collect.get(i);
232             for (int j = i + 1; j < count; j++) {
233                 if (min.intValue() > collect.get(j).intValue()) {
234                     Integer   temp = collect.get(j);
235                     collect.set(j, min);
236                     min = temp;
237                     swaps++;
238                 }
239             }
240             collect.set(i, min);
241         }
242         return swaps;
243     }
244 
245     public int runSort(int count, ObjectArray collect) {
246         int swaps = 0;
247         for (int i = 0; i < count - 1; i++) {
248             Integer   min = (Integer  )collect.get(i);
249             for (int j = i + 1; j < count; j++) {
250                 if (min.intValue() > ((Integer  )collect.get(j)).intValue()) {
251                     Integer   temp = (Integer  )collect.get(j);
252                     collect.set(j, min);
253                     min = temp;
254                     swaps++;
255                 }
256             }
257             collect.set(i, min);
258         }
259         return swaps;
260     }
261 
262     public int runSort(int count, ArrayList collect) {
263         int swaps = 0;
264         for (int i = 0; i < count - 1; i++) {
265             Integer   min = (Integer  )collect.get(i);
266             for (int j = i + 1; j < count; j++) {
267                 if (min.intValue() > ((Integer  )collect.get(j)).intValue()) {
268                     Integer   temp = (Integer  )collect.get(j);
269                     collect.set(j, min);
270                     min = temp;
271                     swaps++;
272                 }
273             }
274             collect.set(i, min);
275         }
276         return swaps;
277     }
278 
279     public int runSort(int count, Vector collect) {
280         int swaps = 0;
281         for (int i = 0; i < count - 1; i++) {
282             Integer   min = (Integer  )collect.elementAt(i);
283             for (int j = i + 1; j < count; j++) {
284                 if (min.intValue() > ((Integer  )collect.elementAt(j)).intValue()) {
285                     Integer   temp = (Integer  )collect.elementAt(j);
286                     collect.setElementAt(min, j);
287                     min = temp;
288                     swaps++;
289                 }
290             }
291             collect.setElementAt(min, i);
292         }
293         return swaps;
294     }
295 
296     /**
297      * Resets the test timer in preparation for running a test.
298      */
299 
300     protected final void startTimer() {
301         startTime = System.currentTimeMillis();
302     }
303 
304     /**
305      * Attempts to trigger a garbage collection in preparation for running a
306      * test.
307      */
308 
309     protected final void cleanMemory() {
310         Runtime   rt = Runtime.getRuntime();
311         rt.gc();
312         try {
313             Thread.sleep(GARBAGE_COLLECT_DELAY);
314         } catch (InterruptedException   ex) {}
315     }
316 
317     /**
318      * Prints the time taken for a particular test run, in tenths of seconds.
319      * This method only generates output if the <code>printFlag</code> value
320      * is <code>true</code>. It assumes the <code>startTimer</code> method was
321      * called prior to the start of the test.
322      *
323      * @param result result value from test run (used for validation)
324      * @param text description text for test
325      */
326 
327     protected void printTestTime(int result, String   text) {
328         if (printFlag) {
329             long time = System.currentTimeMillis() - startTime;
330             System.out.println("Ran " + text + " sort test in " + time + " ms.");
331             if (result != checkResult) {
332                 System.out.println("  Error: test result " + result +
333                     " does not match check value of " + checkResult);
334             }
335         }
336     }
337 
338     /**
339      * Runs the entire sequence of tests. If printing results is enabled, the
340      * results of each timing test are printed immediately after that test is
341      * executed.
342      *
343      * @param count number of values to use in sort collections
344      * @param print flag for printing results
345      * @return sum of all test result values
346      */
347 
348     public int runAllTests(int count, boolean print) {
349 
350         // create and initialize collections
351         int reset = lastValue;
352         cleanMemory();
353         int[] acoll = new int[count];
354         fillCollection(count, acoll);
355         DirectIntArray dicoll = new DirectIntArray(INITIAL_COLLECTION_SIZE);
356         lastValue = reset;
357         fillCollection(count, dicoll);
358         IntArray iacoll = new IntArray(INITIAL_COLLECTION_SIZE);
359         lastValue = reset;
360         fillCollection(count, iacoll);
361         IntegerArray ioacoll = new IntegerArray(INITIAL_COLLECTION_SIZE);
362         lastValue = reset;
363         fillCollection(count, ioacoll);
364         ObjectArray oacoll = new ObjectArray(INITIAL_COLLECTION_SIZE);
365         lastValue = reset;
366         fillCollection(count, oacoll);
367         ArrayList alcoll = new ArrayList(INITIAL_COLLECTION_SIZE);
368         lastValue = reset;
369         fillCollection(count, alcoll);
370         Vector vcoll = new Vector(INITIAL_COLLECTION_SIZE);
371         lastValue = reset;
372         fillCollection(count, vcoll);
373 
374         // print header for test run
375         printFlag = print;
376         if (print) {
377             System.out.println("Starting test run with " + count +
378                 " values to be sorted.");
379         }
380 
381         // run the timing tests
382         int sum = 0;
383         int[] dup = new int[acoll.length];
384         System.arraycopy(acoll, 0, dup, 0, acoll.length);
385         runSort(count/5, dup);
386         cleanMemory();
387         startTimer();
388         int result = checkResult = runSort(count, acoll);
389         printTestTime(result, "int[]");
390         sum += result;
391         runSort(count/5, (DirectIntArray)dicoll.clone());
392         cleanMemory();
393         startTimer();
394         result = runSort(count, dicoll);
395         printTestTime(result, "DirectIntArray");
396         sum += result;
397         runSort(count/5, (IntArray)iacoll.clone());
398         cleanMemory();
399         startTimer();
400         result = runSort(count, iacoll);
401         printTestTime(result, "IntArray");
402         sum += result;
403         runSort(count/5, (IntegerArray)ioacoll.clone());
404         cleanMemory();
405         startTimer();
406         result = runSort(count, ioacoll);
407         printTestTime(result, "IntegerArray");
408         sum += result;
409         runSort(count/5, (ObjectArray)oacoll.clone());
410         cleanMemory();
411         startTimer();
412         result = runSort(count, oacoll);
413         printTestTime(result, "ObjectArray of Integer");
414         sum += result;
415         runSort(count/5, (ArrayList)alcoll.clone());
416         cleanMemory();
417         startTimer();
418         result = runSort(count, alcoll);
419         printTestTime(result, "ArrayList of Integer");
420         sum += result;
421         runSort(count/5, (Vector)vcoll.clone());
422         cleanMemory();
423         startTimer();
424         result = runSort(count, vcoll);
425         printTestTime(result, "Vector of Integer");
426         return sum += result;
427     }
428 
429     /**
430      * Test driver, just reads the input parameters and executes the test.  If
431      * requested, multiple test passes may be run.
432      *
433      * @param argv command line arguments
434      */
435 
436     public static void main(String  [] argv) {
437         if (argv.length > 0) {
438 
439             // parse the parameter values
440             int count = Integer.parseInt(argv[0]);
441             int passes = 0;
442             if (argv.length > 1) {
443                 passes = Integer.parseInt(argv[1]);
444             }
445 
446             // construct the test instance
447             TimeSorts inst = new TimeSorts();
448 
449             // report basic information
450             System.out.println("Java version " + System.getProperty("java.version"));
451             String   text = System.getProperty("java.vm.name");
452             int lines = 1;
453             if (text != null) {
454                 System.out.println(text);
455                 lines++;
456             }
457             text = System.getProperty("java.vm.version");
458             if (text != null) {
459                 System.out.println(text);
460                 lines++;
461             }
462             text = System.getProperty("java.vm.vendor");
463             if (text == null) {
464                 text = System.getProperty("java.vendor");
465             }
466             System.out.println(text);
467 
468             // align headers for convenient printout comparison
469             while (++lines < 5) {
470                 System.out.println("");
471             }
472 
473             // execute the specified number of test passes
474             int sum = 0;
475             if (passes == 0) {
476                 System.out.println("Running initialization pass...");
477                 inst.runAllTests(count / 5, false);
478                 try {
479                     Thread.sleep(DELAY_BETWEEN_TESTS);
480                 } catch (InterruptedException   ex) {}
481                 sum += inst.runAllTests(count, true);
482             } else {
483                 for (int i = 0; i < passes; i++) {
484                     sum += inst.runAllTests(count, true);
485                     if (i < passes) {
486                         try {
487                             Thread.sleep(DELAY_BETWEEN_TESTS);
488                         } catch (InterruptedException   ex) {}
489                     }
490                 }
491             }
492             System.out.println("Check result value " + inst.checkResult);
493 
494         } else {
495             System.out.println("Requires parameters:\n" +
496                 " count - the number of values to be sorted in test\n" +
497                 " [passes] - number of test passes to run (default is single printed\n" +
498                 "            pass after initialization pass with one-fifth the loops\n");
499         }
500     }
501 }
502
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags