|
|
ParellelSorts
RunSortsFromFile.java
package sorts;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.List;
/**
* Run sorting algorithms on test cases read from a file. !!!! Only modify line
* 19 to specify the file to read from !!!! Run starting with 0, and then 1, 2,
* and 3 as you are more confident with your implementations.
*/
public class RunSortsFromFile {
// Modify this line to run a different test file.
// 0: tests_tiny.txt (for debugging--reduce cutoffs to use it.)
// Also feel free to modify tests_tiny.txt as you see fit.
//
// DO NOT CHANGE THE OTHER FILES!
// 1: tests_large.txt
// 2: tests_reallyLarge.txt
// 3: tests_huge.txt
// 4: tests_reallyHuge.txt
private static int TEST_TO_RUN = 1; // <-- Change me for different tests
// --------------------------------------------------------------------
// --------------------------------------------------------------------
// !!! Do not modify below this line !!!
// --------------------------------------------------------------------
// --------------------------------------------------------------------
private static String[] tests = { "tests_tiny.txt",
"tests_large.txt",
"tests_reallyLarge.txt",
"tests_huge.txt",
"tests_reallyHuge.txt" };
// Global accumulators for each algorithm.
private static double[] totalTimes;
private static int[] counts;
public static void main(String[] args) {
String filename = tests[TEST_TO_RUN];
System.out.println("Running tests from file: " + filename);
long startTime = System.nanoTime();
List<String> lines;
try {
lines = Files.readAllLines(Paths.get(filename));
} catch (IOException e) {
System.err.println("Error reading file: " + filename);
return;
}
// Specify the sort algorithm class names.
String[] algorithmClassNames = {
"BuiltInSort",
"QuickSort_MINE",
"ParallelQuickSort_MINE",
"FJQuickSort_MINE" };
// Initialize accumulators for average timing.
totalTimes = new double[algorithmClassNames.length];
counts = new int[algorithmClassNames.length];
// Print header for individual test cases.
System.out.print(" size ");
for (String algorithm : algorithmClassNames) {
SortAlgorithm sortAlgorithm = null;
try {
sortAlgorithm = (SortAlgorithm) Class.forName("chatGPTSorts." + algorithm).getConstructor()
.newInstance();
System.out.printf("%10s ", sortAlgorithm.getName());
} catch (Exception e) {
System.out.println("Error creating sort algorithm: " + algorithm);
System.exit(1);
}
}
System.out.println("");
// Process each non-empty, non-comment line.
for (String line : lines) {
line = line.trim();
if (line.isEmpty() || line.startsWith("#"))
continue;
// The first token is the test type; the second is the array size; remaining
// tokens are parameters.
String[] tokens = line.split("\\s+");
if (tokens.length < 2) {
System.out.println("Skipping invalid test line: " + line);
continue;
}
char type = tokens[0].charAt(0);
int size = Integer.parseInt(tokens[1]);
int[] array = null;
switch (type) {
case 'r':
array = ArrayGenerator.generateRandomArray(size);
break;
case 'i': {
double perturbation = tokens.length >= 3 ? Double.parseDouble(tokens[2]) : 0.05;
array = ArrayGenerator.generateInOrderArray(size, perturbation);
break;
}
case 'o': {
double perturbation = tokens.length >= 3 ? Double.parseDouble(tokens[2]) : 0.05;
array = ArrayGenerator.generateOutOfOrderArray(size, perturbation);
break;
}
case 'm': {
int mod = tokens.length >= 3 ? Integer.parseInt(tokens[2]) : 100;
int offset = tokens.length >= 4 ? Integer.parseInt(tokens[3]) : 0;
array = ArrayGenerator.generateModuloArray(size, mod, offset);
break;
}
case 'c': {
int start = tokens.length >= 3 ? Integer.parseInt(tokens[2]) : 0;
int end = tokens.length >= 4 ? Integer.parseInt(tokens[3]) : 100000;
double clumpFraction = tokens.length >= 5 ? Double.parseDouble(tokens[4]) : 0.1;
int cStart = tokens.length >= 6 ? Integer.parseInt(tokens[5]) : 100;
int cEnd = tokens.length >= 7 ? Integer.parseInt(tokens[6]) : 1000;
array = ArrayGenerator.generateClumpedArrayCustom(size, start, end, clumpFraction, cStart, cEnd);
break;
}
case 'R': {
int start = tokens.length >= 3 ? Integer.parseInt(tokens[2]) : 0;
int end = tokens.length >= 4 ? Integer.parseInt(tokens[3]) : 100000;
double repeatFraction = tokens.length >= 5 ? Double.parseDouble(tokens[4]) : 0.1;
int num = tokens.length >= 6 ? Integer.parseInt(tokens[5]) : 100;
array = ArrayGenerator.generateArrayWithClumpSubset(size, start, end, repeatFraction, num);
break;
}
default:
System.out.println("Unknown test type: " + type);
continue;
}
// Run sorts for this test case.
boolean ranCorrect = runSorts(array, array.length, algorithmClassNames, type);
if (!ranCorrect) {
System.out.println("Test failed for size: " + size + " type: " + type);
System.exit(1);
}
System.out.println();
}
// After processing all test cases, print average times.
System.out.println("Average Times (s):");
for (int i = 0; i < algorithmClassNames.length; i++) {
// Only print an average if at least one test case ran for that algorithm.
if (counts[i] > 0) {
double average = totalTimes[i] / counts[i];
// Using the algorithm name from the header (we assume the class has a getName
// method).
String algName = "";
try {
SortAlgorithm alg = (SortAlgorithm) Class.forName("chatGPTSorts." + algorithmClassNames[i])
.getConstructor().newInstance();
algName = alg.getName();
} catch (Exception e) {
algName = algorithmClassNames[i];
}
System.out.printf("%-10s : %10.4f s%n", algName, average);
}
}
long elapsed = System.nanoTime() - startTime;
double elapsedMin = elapsed / (60 * 1e9);
System.out.printf("\nTotal time %10.6f minutes", elapsedMin);
}
private static boolean runSorts(int[] orig, int size, String[] algorithms, char type) {
System.out.printf("%c: %12d ", type, size);
int[] answer = Arrays.copyOf(orig, orig.length);
long start = System.nanoTime();
Arrays.sort(answer);
long elapsed = System.nanoTime() - start;
double elapsedSec = elapsed / 1e9;
System.out.printf("%10.6f ", elapsedSec);
totalTimes[0] += elapsedSec;
counts[0]++;
for (int i = 1; i < algorithms.length; i++) {
int[] array = Arrays.copyOf(orig, orig.length);
String algorithm = algorithms[i];
SortAlgorithm sortAlgorithm;
try {
sortAlgorithm = (SortAlgorithm) Class.forName("chatGPTSorts." + algorithm).getConstructor()
.newInstance();
} catch (Exception e) {
System.out.println("Error creating sort algorithm: " + algorithm);
return false;
}
start = System.nanoTime();
sortAlgorithm.sort(array);
elapsed = System.nanoTime() - start;
elapsedSec = elapsed / 1e9;
if (Arrays.equals(answer, array)) {
System.out.printf("%10.6f ", elapsedSec);
} else {
System.out.println(" **** Sort incorrect! ****");
return false;
}
totalTimes[i] += elapsedSec;
counts[i]++;
}
return true;
}
}
|