· 8 years ago · Feb 28, 2018, 07:02 PM
1/**
2 * File Name: BenchmarkSorts.java
3 * Date: January 26, 2018
4 * Author: Matt Huffman
5 * Course:
6 * Assignment:
7 * Purpose: This is the class that creates the data sets, runs the sorts, runs the benchmark, calculates the
8 * benchmark data and displays the data.
9 * Created Using: IntelliJ IDEA
10 */
11
12import java.io.*;
13import java.util.Random;
14
15class BenchmarkSorts {
16
17 private int[] setSizes;
18 // This specifies how many times to create random data and sort on each set size.
19 private final int runsPerDataSetSize = 50;
20 // Stores the raw count and time data for each individual sort of every array.
21 private long[][][] recursiveData;
22 private long[][][] iterativeData;
23 // Stores the calculated data of mean and coefficients of variation of count and time for each set size.
24 private double[][] recursiveProcessedData;
25 private double[][] iterativeProcessedData;
26 private MergeSort sort;
27 private File file;
28
29
30 // Constructor
31 BenchmarkSorts(int[] sizes) {
32 this.setSizes = sizes;
33 sort = new MergeSort();
34 }
35
36 // Method to run the sorts.
37 void runSorts() {
38
39 // Create the file to store the verification printout.
40 file = new File("VerifySort.txt");
41 recursiveData = new long[setSizes.length][2][runsPerDataSetSize];
42 iterativeData = new long[setSizes.length][2][runsPerDataSetSize];
43
44 // Check to see if file exists and delete so the file does not get appended to on each run of this program.
45 if (file.delete()) {
46 System.out.println("Deleted previous VerifySort.txt file.\n");
47 } else {
48 System.out.println("VerifySort.txt file created.\n");
49 }
50
51 // Outer loop for each data set size.
52 for (int i = 0; i < setSizes.length; i++) {
53 // Inner loop to run a set number of sorts of each size.
54 for (int j = 0; j < runsPerDataSetSize; j++) {
55 int[] dataSet = generateArray(setSizes[i]);
56 int[] recursiveSet = new int[dataSet.length];
57 int[] iterativeSet = new int[dataSet.length];
58 System.arraycopy(dataSet, 0, recursiveSet, 0, dataSet.length);
59 System.arraycopy(dataSet, 0, iterativeSet, 0, dataSet.length);
60
61 try {
62 sort.recursiveSort(recursiveSet);
63 recursiveData[i][0][j] = sort.getCount();
64 recursiveData[i][1][j] = sort.getTime();
65 sort.iterativeSort(iterativeSet);
66 iterativeData[i][0][j] = sort.getCount();
67 iterativeData[i][1][j] = sort.getTime();
68 } catch (UnsortedException e) {
69 System.out.println("Array Not Sorted: " + e.getMessage());
70 }
71 // Will print out the set that half the total sets to a file for verification the sort works.
72 if (j == runsPerDataSetSize/2) {
73 printArray(dataSet, recursiveSet, iterativeSet);
74 }
75 }
76 }
77 } // End runSorts method.
78
79 // Method to generate the array with random numbers within a set range specified by size parameter.
80 private int[] generateArray(int size) {
81
82 int[] dataSet = new int[size];
83 Random rand = new Random();
84
85 for (int i = 0; i < size; i++) {
86 dataSet[i] = rand.nextInt(size);
87 }
88 return dataSet;
89 } // End generateArray method.
90
91 // Method to print the contents of the original unsorted array and the recursive and iterative sorted arrays to a
92 // file for verification that the sort works.
93 private void printArray(int unsorted[], int recSorted[], int iterSorted[]) {
94 try {
95 FileWriter fw = new FileWriter(file, true);
96 BufferedWriter bw = new BufferedWriter(fw);
97 PrintWriter pw = new PrintWriter(bw);
98
99 pw.println();
100 pw.println("Showing the contents of the unsorted, recursive sorted, and iterative sorted arrays, for data" +
101 " set size: " + unsorted.length);
102 pw.println();
103 pw.printf("%12s%12s%12s%n", "Unsorted", "Recursive", "Iterative");
104 pw.printf("%12s%12s%12s%n", "-----------", "-----------", "-----------");
105 for (int i = 0; i < unsorted.length; i++) {
106 pw.printf("%12s%12s%12s%n", unsorted[i], recSorted[i], iterSorted[i]);
107 }
108 pw.println();
109 pw.close();
110 } catch (IOException er) {
111 System.out.println("File Not Found: " + er.getMessage());
112 }
113 }// End printArray method.
114
115 // Method to calculate and store the mean and coefficient of variation data.
116 void calculateData() {
117
118 // Stores the sums.
119 long a, b, c, d;
120 // Stores the mean data.
121 double s, t, u, v;
122 // Used to calculate and store the standard deviation.
123 double w, x, y, z;
124 // Used to convert time to milliseconds.
125 double xx, yy;
126 recursiveProcessedData = new double[setSizes.length][4];
127 iterativeProcessedData = new double[setSizes.length][4];
128
129 // Get total sum for mean.
130 for (int i = 0; i < setSizes.length; i++) {
131 a = b = c = d = 0;
132 w = x = y = z = 0;
133 for (int j = 0; j < runsPerDataSetSize; j++) {
134 a += recursiveData[i][0][j];
135 b += recursiveData[i][1][j];
136 c += iterativeData[i][0][j];
137 d += iterativeData[i][1][j];
138 }
139 // Calculate and store the mean for recursive and iterative count and time.
140 s = (double) a / runsPerDataSetSize;
141 t = (double) b / runsPerDataSetSize;
142 xx = t / 1000000;
143 u = (double) c / runsPerDataSetSize;
144 v = (double) d / runsPerDataSetSize;
145 yy = v / 1000000;
146 recursiveProcessedData[i][0] = s;
147 recursiveProcessedData[i][2] = xx;
148 iterativeProcessedData[i][0] = u;
149 iterativeProcessedData[i][2] = yy;
150
151 // Calculate the standard deviation - sums of (data - mean)^2.
152 for (int k = 0; k < runsPerDataSetSize; k++) {
153 w += ((recursiveData[i][0][k] - s) * (recursiveData[i][0][k] - s));
154 x += ((recursiveData[i][1][k] - t) * (recursiveData[i][1][k] - t));
155 y += ((iterativeData[i][0][k] - u) * (iterativeData[i][0][k] - u));
156 z += ((iterativeData[i][1][k] - v) * (iterativeData[i][1][k] - v));
157 }
158
159 // Finish the calculation to get the standard deviation, Sqrt(sum / number of items in set - 1)
160 w = Math.sqrt(w / (runsPerDataSetSize - 1));
161 x = Math.sqrt(x / (runsPerDataSetSize - 1));
162 y = Math.sqrt(y / (runsPerDataSetSize - 1));
163 z = Math.sqrt(z / (runsPerDataSetSize - 1));
164
165 // Calculate and store the coefficient of variation for recursive and iterative count and time.
166 // (Standard Deviation / Mean)
167 recursiveProcessedData[i][1] = w / s;
168 recursiveProcessedData[i][3] = x / t;
169 iterativeProcessedData[i][1] = y / u;
170 iterativeProcessedData[i][3] = z / v;
171 }
172 } // End calculateData method.
173
174 // Method to display the mean and COV of count and time, formatted into a table for readability. The formatting
175 // values used allow for data set sizes much larger as well as the mean values to be much larger before
176 // formatting gets misaligned.
177 void displayReport() {
178 System.out.println("--------------------------------------------------------------------------------" +
179 "----------------------------------");
180 System.out.printf("|%-10s|%-49s|||%-49s|%n", "Data Set", " Recursive",
181 " Iterative");
182 System.out.printf("|%-10s|%-49s|||%-49s|%n", "Size N", "", "");
183 System.out.println("--------------------------------------------------------------------------------" +
184 "----------------------------------");
185 System.out.printf("|%-10s|%-15s|%-8s|%-15s|%-8s|||%-15s|%-8s|%-15s|%-8s|%n", "", "Mean", "Count", "Mean Time",
186 "Time", "Mean", "Count", "Mean Time", "Time");
187 System.out.printf("|%-10s|%-15s|%-8s|%-15s|%-8s|||%-15s|%-8s|%-15s|%-8s|%n", "", "Count", "COV", "" +
188 "(milliseconds)", "COV", "Count", "COV", "(milliseconds)", "COV");
189 System.out.println("--------------------------------------------------------------------------------" +
190 "----------------------------------");
191 for (int i = 0; i < setSizes.length; i++) {
192 System.out.printf("|%-10s|%-15.2f|%-8.5f|%-15.4f|%-8.5f|||%-15.2f|%-8.5f|%-15.4f|%-8.5f|%n",
193 setSizes[i], recursiveProcessedData[i][0], recursiveProcessedData[i][1],
194 recursiveProcessedData[i][2], recursiveProcessedData[i][3], iterativeProcessedData[i][0],
195 iterativeProcessedData[i][1], iterativeProcessedData[i][2], iterativeProcessedData[i][3]);
196 }
197 System.out.println("--------------------------------------------------------------------------------" +
198 "----------------------------------");
199 } // End displayReport method.
200}