InitHEADmain

1 files changed, 238 insertions, 0 deletions

diff --git a/Homework/cs3460/array_perf/sortutils.cpp b/Homework/cs3460/array_perf/sortutils.cpp
new file mode 100644
index 0000000..402f561
--- /dev/null
+++ b/Homework/cs3460/array_perf/sortutils.cpp
@@ -0,0 +1,238 @@
+#include "sortutils.hpp"
+
+/**
+ * @struct SortResult stores simple information about a sorting time result
+ */
+struct SortResult
+{
+    std::string title;
+    std::uint64_t duration;
+};
+
+/**
+ * @param std::string sequentialString: use "Sequential" or "Parallel"
+ * @param std::vector<struct SortResult>: the list of results from a sorting run
+ * @return void: format all the sorting results according to program requirements
+ */
+void formatSortResults(std::string sequentialString, const std::vector<struct SortResult>& results)
+{
+    const std::string timeStr = " Time";
+    std::uint32_t longestTitle = static_cast<std::uint32_t>(std::max_element(
+                                                                results.begin(),
+                                                                results.end(),
+                                                                [](const struct SortResult s1, const struct SortResult s2) { return s1.title.length() < s2.title.length(); })
+                                                                ->title.length());
+    std::cout << sequentialString << std::endl;
+    for (auto sortResult : results)
+    {
+        std::cout << fmt::format("\t{0:<{1}} : {2} ms", sortResult.title + timeStr, longestTitle + timeStr.length(), sortResult.duration)
+                  << std::endl;
+    }
+    std::cout << std::endl;
+}
+
+/**
+ * @param std::string title: title of the array type used
+ * @param std::vector<struct SortResult> sequentialResults: list of results of sequential sorts
+ * @param std::vector<struct SortResult> parallelResults: list of results of parallel sorts
+ * @return void: format the results and title according to program requirements
+ */
+void formatArrayTypeSortResults(std::string title, const std::vector<struct SortResult>& sequentialResults, const std::vector<struct SortResult>& parallelResults)
+{
+    std::cout << fmt::format("  --- {0} Performance ---", title) << std::endl;
+    formatSortResults("Sequential", sequentialResults);
+    formatSortResults("Parallel", parallelResults);
+}
+
+/**
+ * @param SourceArray source: source array to copy into->
+ * @param int[] dest: the raw array to copy source's elements to
+ * @return void: do the copy
+ */
+void initializeRawArrayFromStdArray(const SourceArray& source, int dest[])
+{
+    std::copy(std::execution::par, source.begin(), source.end(), dest);
+}
+
+/**
+ * @param SourceArray data: the source data to convert into a "organ pipe" array per program requirements
+ * @return void: do the piping
+ */
+void organPipeStdArray(SourceArray& data)
+{
+    float mid = HOW_MANY_ELEMENTS / 2.0;
+    std::reverse_copy(std::execution::par, data.begin(), data.begin() + static_cast<std::uint32_t>(std::floor(mid)), data.begin() + static_cast<std::uint32_t>(std::ceil(mid)));
+}
+
+/**
+ * @param function<void()> func: the function to time
+ * @return uint64_t: the milliseconds required to execute func()
+ */
+std::uint64_t executionMs(std::function<void()> func)
+{
+    std::chrono::time_point start = std::chrono::steady_clock::now();
+    func();
+    return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count();
+}
+
+/**
+ * @param SourceArray source: the values to copy into rawArray HOW_MANY_TIMES times
+ * @param int[] rawArray: the raw array to benchmark
+ * @param bool parallel: whether to use parallel execution
+ * @return uint64_t: time (in ms) to sort copied values from source -> rawArray HOW_MANY_TIMES times
+ */
+std::uint64_t totalTimeToSortRawArrayManyTimes(const SourceArray& source, int rawArray[], bool parallel)
+{
+    std::uint64_t ms = 0;
+    for (std::uint32_t i = 0; i < HOW_MANY_TIMES; i++)
+    {
+        initializeRawArrayFromStdArray(source, rawArray);
+        if (parallel)
+        {
+            ms += executionMs([&rawArray]() -> void { std::sort(std::execution::par_unseq, rawArray, rawArray + HOW_MANY_ELEMENTS); });
+        }
+        else
+        {
+            ms += executionMs([&rawArray]() -> void { std::sort(std::execution::seq, rawArray, rawArray + HOW_MANY_ELEMENTS); });
+        }
+    }
+    return ms;
+}
+
+/**
+ * @param SourceArray source: the values to copy into rawArray HOW_MANY_TIMES times
+ * @param SourceArray stdArray: the std::array to benchmark
+ * @param bool parallel: whether to use parallel execution
+ * @return uint64_t: time (in ms) to sort copied values from source -> stdArray HOW_MANY_TIMES times
+ */
+std::uint64_t totalTimeToSortStdArrayManyTimes(const SourceArray& source, SourceArray& stdArray, bool parallel)
+{
+    std::uint64_t ms = 0;
+    for (std::uint32_t i = 0; i < HOW_MANY_TIMES; i++)
+    {
+        std::copy(source.begin(), source.end(), stdArray.begin());
+        if (parallel)
+        {
+            ms += executionMs([&stdArray]() -> void { std::sort(std::execution::par_unseq, stdArray.begin(), stdArray.end()); });
+        }
+        else
+        {
+            ms += executionMs([&stdArray]() -> void { std::sort(std::execution::seq, stdArray.begin(), stdArray.end()); });
+        }
+    }
+    return ms;
+}
+
+/**
+ * @param SourceArray source: the values to copy into rawArray HOW_MANY_TIMES times
+ * @param SourceArray stdVector: the vector to benchmark
+ * @param bool parallel: whether to use parallel execution
+ * @return uint64_t: time (in ms) to sort copied values from source -> stdVector HOW_MANY_TIMES times
+ */
+std::uint64_t totalTimeToSortStdVectorManyTimes(const SourceArray& source, std::vector<int>& stdVector, bool parallel)
+{
+    std::uint64_t ms = 0;
+    for (std::uint32_t i = 0; i < HOW_MANY_TIMES; i++)
+    {
+        std::copy(source.begin(), source.end(), stdVector.begin());
+        if (parallel)
+        {
+            ms += executionMs([&stdVector]() -> void { std::sort(std::execution::par_unseq, stdVector.begin(), stdVector.end()); });
+        }
+        else
+        {
+            ms += executionMs([&stdVector]() -> void { std::sort(std::execution::seq, stdVector.begin(), stdVector.end()); });
+        }
+    }
+    return ms;
+}
+
+/**
+ * @param SourceArray random: a list of random values initialize in main.cpp
+ * @param SourceArray sorted: random, but sorted in sequential order
+ * @param SourceArray reversed: sorted, but reversed
+ * @param SourceArray organPipe: sorted, but "organ-piped"
+ * @param SourceArray rotated: sorted, but rotated by one
+ * @return void: format results of the raw array benchmark
+ */
+void evaluateRawArray(const SourceArray& random, const SourceArray& sorted, const SourceArray& reversed, const SourceArray& organPipe, const SourceArray& rotated)
+{
+    int rawArray[HOW_MANY_ELEMENTS];
+    std::vector<struct SortResult> seqResults{
+        { "Random", totalTimeToSortRawArrayManyTimes(random, rawArray, false) },
+        { "Sorted", totalTimeToSortRawArrayManyTimes(sorted, rawArray, false) },
+        { "Reversed", totalTimeToSortRawArrayManyTimes(reversed, rawArray, false) },
+        { "Organ Piped", totalTimeToSortRawArrayManyTimes(organPipe, rawArray, false) },
+        { "Rotated", totalTimeToSortRawArrayManyTimes(rotated, rawArray, false) },
+    };
+
+    std::vector<struct SortResult> parResults{
+        { "Random", totalTimeToSortRawArrayManyTimes(random, rawArray, true) },
+        { "Sorted", totalTimeToSortRawArrayManyTimes(sorted, rawArray, true) },
+        { "Reversed", totalTimeToSortRawArrayManyTimes(reversed, rawArray, true) },
+        { "Organ Piped", totalTimeToSortRawArrayManyTimes(organPipe, rawArray, true) },
+        { "Rotated", totalTimeToSortRawArrayManyTimes(rotated, rawArray, true) },
+    };
+
+    formatArrayTypeSortResults("Raw Array", seqResults, parResults);
+}
+
+/**
+ * @param SourceArray random: a list of random values initialize in main.cpp
+ * @param SourceArray sorted: random, but sorted in sequential order
+ * @param SourceArray reversed: sorted, but reversed
+ * @param SourceArray organPipe: sorted, but "organ-piped"
+ * @param SourceArray rotated: sorted, but rotated by one
+ * @return void: format results of the std array benchmark
+ */
+void evaluateStdArray(const SourceArray& random, const SourceArray& sorted, const SourceArray& reversed, const SourceArray& organPipe, const SourceArray& rotated)
+{
+    SourceArray stdArray;
+    std::vector<struct SortResult> seqResults{
+        { "Random", totalTimeToSortStdArrayManyTimes(random, stdArray, false) },
+        { "Sorted", totalTimeToSortStdArrayManyTimes(sorted, stdArray, false) },
+        { "Reversed", totalTimeToSortStdArrayManyTimes(reversed, stdArray, false) },
+        { "Organ Piped", totalTimeToSortStdArrayManyTimes(organPipe, stdArray, false) },
+        { "Rotated", totalTimeToSortStdArrayManyTimes(rotated, stdArray, false) },
+    };
+
+    std::vector<struct SortResult> parResults{
+        { "Random", totalTimeToSortStdArrayManyTimes(random, stdArray, true) },
+        { "Sorted", totalTimeToSortStdArrayManyTimes(sorted, stdArray, true) },
+        { "Reversed", totalTimeToSortStdArrayManyTimes(reversed, stdArray, true) },
+        { "Organ Piped", totalTimeToSortStdArrayManyTimes(organPipe, stdArray, true) },
+        { "Rotated", totalTimeToSortStdArrayManyTimes(rotated, stdArray, true) },
+    };
+
+    formatArrayTypeSortResults("std::array", seqResults, parResults);
+}
+
+/**
+ * @param SourceArray random: a list of random values initialize in main.cpp
+ * @param SourceArray sorted: random, but sorted in sequential order
+ * @param SourceArray reversed: sorted, but reversed
+ * @param SourceArray organPipe: sorted, but "organ-piped"
+ * @param SourceArray rotated: sorted, but rotated by one
+ * @return void: format results of the std vector benchmark
+ */
+void evaluateStdVector(const SourceArray& random, const SourceArray& sorted, const SourceArray& reversed, const SourceArray& organPipe, const SourceArray& rotated)
+{
+    std::vector<int> stdVector(HOW_MANY_ELEMENTS);
+    std::vector<struct SortResult> seqResults{
+        { "Random", totalTimeToSortStdVectorManyTimes(random, stdVector, false) },
+        { "Sorted", totalTimeToSortStdVectorManyTimes(sorted, stdVector, false) },
+        { "Reversed", totalTimeToSortStdVectorManyTimes(reversed, stdVector, false) },
+        { "Organ Piped", totalTimeToSortStdVectorManyTimes(organPipe, stdVector, false) },
+        { "Rotated", totalTimeToSortStdVectorManyTimes(rotated, stdVector, false) },
+    };
+
+    std::vector<struct SortResult> parResults{
+        { "Random", totalTimeToSortStdVectorManyTimes(random, stdVector, true) },
+        { "Sorted", totalTimeToSortStdVectorManyTimes(sorted, stdVector, true) },
+        { "Reversed", totalTimeToSortStdVectorManyTimes(reversed, stdVector, true) },
+        { "Organ Piped", totalTimeToSortStdVectorManyTimes(organPipe, stdVector, true) },
+        { "Rotated", totalTimeToSortStdVectorManyTimes(rotated, stdVector, true) },
+    };
+
+    formatArrayTypeSortResults("std::vector", seqResults, parResults);
+}